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

[구슬찾기]

# 문제
모양은 같으나, 무게가 모두 다른 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 개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.

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

0. 풀이 방법

문제에서 주어진 무게 정보를 반대로 뒤집어서 추가 정보를 얻을 수 있다.

 

쓸데없는 말 싹 빼버리고~

 

이 정보를 가지고 대소 관계를 정리할 수 있다.

 

여기까지가 문제에서 주어진 정보이고,
여기에서 파고 들어가면 이 문제를 풀 수 있다!

 

새로운 정보 1

1️⃣ 2<4 2번이 4번보다 작고
2️⃣ 1<2 1번이 2번보다 작으니까
👉 1<2<4 1번은 4번보다 작다.

 

새로운 정보 2

마찬가지로,
1️⃣ 2>1 2번이 1번보다 크고
2️⃣ 4>2 4번이 2번보다 크니
👉 4>2>1 4번은 1번보다 크다.

 

결론

1번보다 큰 애들이 3개이고,
4번보다 작은 애들이 3개가 되어서
이 둘은 중간 값이 될 수 없는 것들로 당첨이다!

 

코드로 옮기려면 DFS를 활용하면 된다.

 

예를 들어, 2번 구슬보다 더 작은 구슬의 개수를 구할 때는
2번 구슬보다 더 작은 1번 구슬을 타고 가서 그 1번 구슬보다 더 작은 구슬의 개수를 모조리 세어오는 식으로 타고 가는 것이다.

연결된 게 더이상 없을 때까지!

 

1. 대소관계 정리

• 더 무거운 것들만 담을 리스트와 더 가벼운 것들만 담을 리스트 각각 하나씩 총 두 개를 만들어준다.
• heavy_list[구슬번호]에는 인덱스에 해당하는 구슬보다 무거운 구슬의 번호들을 리스트 형태로 담아주고,
  반대로 light_list[구슬번호]에는 인덱스에 해당하는 구슬보다 가벼운 구슬의 번호들을 리스트 형태로 담아준다.

heavy_list = [[] for _ in range(N+1)]  # heavy_list[노드] = [노드보다 무거운 것들]
light_list = [[] for _ in range(N+1)]  # light_list[노드] = [노드보다 가벼운 것들]

for _ in range(M):
    heavy, light = map(int, sys.stdin.readline().split())
    heavy_list[heavy].append(light)
    light_list[light].append(heavy)

 

2. 연결된 구슬 개수 구하기

• 이 함수를 호출할 때
  무거운 구슬을 구할 때는 인자로 heavy_list를 보내고,
  가벼운 구슬을 구할 때는 인자로 light_list를 보내준다.
• DFS 함수 안에서는 전달 받은 list에서 root노드가 연결된 구슬들의 개수를 구해서 return해준다.

def DFS(list, root):
    """root보다 가볍거나/무거운 것의 개수 구하는 함수"""
    count = 0
    for node in list[root]:
        if not visited[node]:  # 방문하지 않았으면
            visited[node] = True  # 방문 처리
            count += 1
            count += DFS(list, node)
    return count

 

3. 중간값이 가능한지 검증

• 어떤 구슬보다 가볍거나 무거운 구슬의 개수가 (N+1)/2인 mid 이상이 되면 이 구슬은 중간값이 될 수 없다.

mid = (N+1)/2
result = 0

for root in range(1, N+1):  # index로 list에 바로 접근하기 위해 1부터 반복
    visited = [False] * (N+1)
    if DFS(heavy_list, root) >= mid:
        result += 1
    if DFS(light_list, root) >= mid:
        result += 1

print(result)

 

끝!

전체 코드

import sys
N, M = map(int, input().split())

heavy_list = [[] for _ in range(N+1)]  # heavy_list[노드] = [노드보다 무거운 것들]
light_list = [[] for _ in range(N+1)]  # light_list[노드] = [노드보다 가벼운 것들]

for _ in range(M):
    heavy, light = map(int, sys.stdin.readline().split())
    heavy_list[heavy].append(light)
    light_list[light].append(heavy)


def DFS(list, root):
    """root보다 가볍거나/무거운 것의 개수 구하는 함수"""
    count = 0
    for node in list[root]:
        if not visited[node]:  # 방문하지 않았으면
            visited[node] = True  # 방문 처리
            count += 1
            count += DFS(list, node)
    return count


mid = (N+1)/2
result = 0

for root in range(1, N+1):
    visited = [False] * (N+1)
    if DFS(heavy_list, root) >= mid:
        result += 1
    if DFS(light_list, root) >= mid:
        result += 1

print(result)