[python] 백준 > DFS > 구슬찾기(2617)

[문제]

모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아래와 같은 일을 하려 한다.

우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운가를 알 수 있다. 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운가를 모두 알아냈다. 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다.

예를 들어, N=5이고, M=4 쌍의 구슬에 대해서 어느 쪽이 무거운가를 알아낸 결과가 아래에 있다.

1. 구슬 2번이 구슬 1번보다 무겁다.
2. 구슬 4번이 구슬 3번보다 무겁다.
3. 구슬 5번이 구슬 1번보다 무겁다.
4. 구슬 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 개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.

출력

첫 줄에 무게가 중간이 절대로 될 수 없는 구슬의 수를 출력 한다.

 

[풀이]

from collections import defaultdict

def dfs(node, weight):
    global cnt
    visited[node] = True
    for n in weight[node]:
        if not visited[n]:
            cnt += 1
            dfs(n, weight)
    return cnt

if __name__ == '__main__':    
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(M)]
    result = 0

    light = defaultdict(list)
    heavy = defaultdict(list)

    for x, y in arr:
        heavy[x].append(y)
        light[y].append(x)

    for i in range(1, N+1):
        visited = [False]*(N+1)
        cnt = 0
        if dfs(i, heavy) >= (N+1)//2:
            result += 1
        cnt = 0
        if dfs(i, light) >= (N+1)//2:
            result += 1
    print(result)

 

• 처음에 문제 이해하기가 너무 어려웠다.
• 어떤 값이 다른 값보다 크거나 작은 갯수가 전체갯수의 반개 이상이라면 그것은 절때 중간 값이 될 수 없다.
• 그래서 일단 현재 값을 기준으로 연결돼있는 노드 갯수를 구하고 그 갯수가 (N+1)//2개 이상이면 result에 1을 더해준뒤 값을 구한다.
• defaultdict를 사용하니 굉장히 편리했다.
• 따로 N+1개의 리스트를 만들어 넣어줄 필요 없이 노드 값을 key값으로 해당 노드에 연결돼있는 노드값을 value값으로 넣어준 뒤에 관리하였다.
• 그리고 큰 값과 작은값 두개를 구해야 하는데 그럴려면 노드 방향을 하나는 똑바로 하나는 반대로 한 뒤에 비교해야 했다.(이부분을 놓쳤다)

[다른 사람의 풀이]

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = {i:[] for i in range(1,n+1)}
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append((b,True)) 
    graph[b].append((a, False))  
def bfs(start):
    dq = deque()
    check_greater, check_less = set(), set()
    dq.append((start, False))
    dq.append((start, True))
    while dq:
        node, s = dq.popleft()
        if len(check_greater) > n // 2 or len(check_less) > n // 2:
            return 1
        for n_n, n_s in graph[node]:
            if (n_n not in check_greater) and (n_n not in check_less):
                if (not s) and (not n_s):
                    dq.append((n_n, n_s))
                    check_greater.add(n_n)
                elif s and n_s:
                    dq.append((n_n, n_s))
                    check_less.add(n_n)
    return 0
count = 0
for i in range(1, n+1):
    count += bfs(i)
print(count)

• graph에 넣어줄 때 기준 값보다 큰지 작은지 True, False로 구분해서 넣어줬다.
• check를 두가지로 만들어서 현재 구슬보다 큰지 작은지 구분해서 방문 체크했다.