소스코드
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N, M = map(int, input().strip().split())
heavy_graph = [[] for _ in range(N+1)] # 더 무거운 방향으로 연결
light_graph = [[] for _ in range(N+1)] # 더 가벼운 방향으로 연결
# 연결관계 설정
for _ in range(M):
heavy, light = map(int, input().strip().split())
heavy_graph[light].append(heavy)
light_graph[heavy].append(light)
# DFS 카운트
def dfs(graph, visited, node):
count = 0
visited[node] = True
# 인접 노드 탐색
for next_node in graph[node]:
if not visited[next_node]:
visited[next_node] = True
count += 1
count += dfs(graph, visited, next_node)
return count
result = 0
for i in range(1, N+1):
heavy_count = dfs(heavy_graph, [False] * (N+1), i)
if heavy_count >= ((N + 1) // 2):
result += 1
continue
light_count = dfs(light_graph, [False] * (N+1), i)
if light_count >= ((N + 1) // 2):
result += 1
continue
# 결과 출력
print(result)
Python
복사
풀이
•
예제 입력에 대해 대소 비교를 표현해보면, 절대 중간이 될 수 없는 기준에 대해 생각해보게 됩니다. 이때 1번 구슬보다 무거운 것이 2,4,5번 구슬이고 4번 구슬보다 가벼운 것이 1,2,3번이라고 나오는데, 공통점을 유심히 보다보면 모두 총 개수의 절반 이상이 있으면 중간이 절대 될 수 없는 것이구나라고 생각해볼 수 있습니다.
•
M은 저울에 올려 본 쌍의 개수라고 했잖아요? 그래서 연결 관계(= 간선)을 먼저 떠올려보게 되었습니다. 상대적인 무게 비교가 존재하므로 무방향보다는 무가중치 방향 그래프로 표현해볼 수 있습니다.
◦
해당 그래프를 그림으로 표현해보면, 연결된 노드들의 개수를 세어볼 수 있겠다는 생각이 떠오를테고, 이는 곧 DFS로 생각을 연결해볼 수 있습니다.
•
그렇다고 하나의 그래프에 이 관계들을 표현하긴 조금 버겁다고 생각했습니다. 대소관계가 명확한데 이를 양방향으로 표현하는건 옳지 않으니까요.
◦
그래서 2개의 그래프로 만들었습니다.
◦
입력 쌍에서 앞의 값과 뒤의 값이 각각 더 무거운 것과 가벼운 것이니, 두 개의 그래프에 방향을 적절하게 설정해주면 되겠죠?
•
모든 노드에 대해, 두 개의 그래프를 이용해서 절대 중간 구슬이 될 수 없는 노드를 찾아냅니다.
•
결과 출력하면 끝!!
회고
•
항상 하나의 자료구조는 잘 떠올리고 확신을 갖기 좋은데, 두 개 이상의 자료구조를 사용하려고 하면 피하게 되는 것 같습니다. 좀 더 비슷한 유형의 문제들을 계속 도전해보면서 이런 경우마다 확신을 못 갖고 시작을 망설이는 경우에 대해 확신을 가질 수 있도록 단련해야할 것 같습니다.
•
DFS나 BFS 문제에서, 항상 바깥의 로직을 이용해서 함수에는 어떤 인자들을 넘기고 결과를 어떻게 반영할 지를 먼저 틀을 잡고 시작하면 작성 속도에 확신을 갖고 빠르게 코드를 작성하는 것 같습니다. 이를 계속 이어나가야겠습니다.