[백준] [파이썬] [Graph] [BFS] [DFS] 2617번: 구슬 찾기
문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog
문제
모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아래와 같은 일을 하려 한다.
우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운가를 알 수 있다. 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운가를 모두 알아냈다. 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다.
예를 들어, N=5이고, M=4 쌍의 구슬에 대해서 어느 쪽이 무거운가를 알아낸 결과가 아래에 있다.
- 구슬 2번이 구슬 1번보다 무겁다.
- 구슬 4번이 구슬 3번보다 무겁다.
- 구슬 5번이 구슬 1번보다 무겁다.
- 구슬 4번이 구슬 2번보다 무겁다.
위와 같이 네 개의 결과만을 알고 있으면, 무게가 중간인 구슬을 정확하게 찾을 수는 없지만, 1번 구슬과 4번 구슬은 무게가 중간인 구슬이 절대 될 수 없다는 것은 확실히 알 수 있다. 1번 구슬보다 무거운 것이 2, 4, 5번 구슬이고, 4번 보다 가벼운 것이 1, 2, 3번이다. 따라서 답은 2개이다.
M 개의 쌍에 대한 결과를 보고 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램을 작성하시오.
입력
첫 줄은 구슬의 개수를 나타내는 정수 N(1 ≤ N ≤ 99)과 저울에 올려 본 쌍의 개수 M(1 ≤ M ≤ N(N-1)/2)이 주어진다. 그 다음 M 개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.
출력
첫 줄에 무게가 중간이 절대로 될 수 없는 구슬의 수를 출력 한다.
예제 입력 1
5 4
2 1
4 3
5 1
4 2
예제 출력 1
2
그림을 그려봐야한다.
한 구슬이 뭐보다 크고 뭐보다 크고 이렇게 언급이 많으면 일단 중간값은 될 수 없을 것이다.
또 한 구슬이 뭐보다 작고 뭐보다 작고 이렇게 언급이 많으면 중간값이 될 수 없다.
따라서 '큰 구슬 그룹'관점에서 봤을때 노드를 타고 타고 내려갔을때 카운트되는 수가 중간값(N+1/2)보다 크면 중간값이 될 수 없을 것이고 '작은 구슬 그룹'관점에서 봤을때 노드를 타고 타고 내려갔을때 카운트되는 수가 중간값(N+1/2)보다 크면 중간값이 될 수 없을 것이다.
따라서 큰 구슬 관점의 리스트와 작은 구슬 관점의 리스트를 각각 만들고 각 구슬별로 몇개의 노드가 연결되는지 카운트하면서 중간값보다 큰지 작은지를 확인하면 될것이다. 이때 잊지 말아야 할 것은 노드를 방문하고 다시 올라가서 방문한 노드를 중복 방문하는 일이 없어야 한다.
BFS로 푼 코드
import sys
from collections import deque
sys.stdin=open('input.txt','r')
def BFS(x,graph):
cnt=0
visited[x]=True
Q=deque()
Q.append(x)
while Q:
e=Q.popleft()
for i in graph[e]:
if not visited[i]:
cnt+=1
visited[i]=True
Q.append(i)
return cnt
if __name__=="__main__":
N,M=map(int, input().split())
graph1=[[] for _ in range(N+1)]
graph2=[[] for _ in range(N+1)]
mid=(N+1)/2
for _ in range(M):
a,b=map(int, input().split())
graph1[b].append(a)
graph2[a].append(b)
ans=0
for i in range(1,N+1):
cnt=0
visited=[False]*(N+1)
if BFS(i,graph1)>=mid:
ans+=1
cnt=0
if BFS(i,graph2)>=mid:
ans+=1
print(ans)DFS로 푼 코드
import sys
from collections import deque
sys.stdin=open('input.txt','r')
def DFS(x,graph):
global cnt
for e in graph[x]:
if not visited[e]: # False면, 즉 첫 방문일때만
visited[e]=True
cnt+=1
DFS(e,graph)
if __name__=="__main__":
N,M=map(int, input().split())
graph1=[[] for _ in range(N+1)]
graph2=[[] for _ in range(N+1)]
mid=(N+1)/2
for _ in range(M):
a,b=map(int, input().split())
graph1[b].append(a)
graph2[a].append(b)
ans=0
for i in range(1,N+1):
cnt=0
visited=[False]*(N+1)
DFS(i,graph1)
if cnt>=mid:
ans+=1
cnt=0
DFS(i,graph2)
if cnt>=mid:
ans+=1
print(ans)
플로이드 워샬로 풀기
import sys
input = sys.stdin.readline
# 모든 구슬들의 관계를 살펴보고 조건 확인하기
N, M = map(int, input().split())
arr = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
s, e = map(int, input().split())
arr[s][e] = 1
# 플로이드 와샬
for k in range(1, N+1):
for i in range(1, N+1):
for j in range(1, N+1):
if arr[i][k] and arr[k][j]:
arr[i][j] = 1
ans = 0
for i in range(1, N+1):
left_cnt = 0
right_cnt = 0
for j in range(1, N+1):
if i == j:
continue
elif arr[i][j] == 1: # 현재 구슬보다 가벼운 갯수 세기
right_cnt += 1
elif arr[j][i] == 1:# 현재 구슬 보다 무거운 갯수 세기
left_cnt += 1
if right_cnt > N//2 or left_cnt > N//2: # 가볍거나 무거운 개수가 중간값 보다 많으면 될 수가 없다
ans += 1
print(ans)