문제 설명
어느날, 한 마을에서 선물 전달을 위한 특별한 이벤트가 열렸습니다. 이 이벤트의 목적은 서로 다른 사람들 간에 선물을 전달하는 것입니다. n명의 참가자가 있으며, 각 참가자는 정확히 한 개의 선물을 전달해야 합니다. 하지만 선물을 전달할 수 있는 상대방에 대한 제약사항이 있습니다.
모든 참가자는 누가 누구에게 선물을 전달할 수 있는지를 나타내는 연결 리스트 또는 배열을 갖고 있습니다. 이 제약사항을 고려했을 때, 모든 참가자가 선물을 전달할 수 있는지, 즉 모든 참가자가 선물을 받게 할 수 있는지 확인해야 합니다.
입력 형식
첫 번째 줄에는 참가자의 수 n이 주어집니다. 그 다음 줄에는 n명의 참가자가 선물을 전달할 수 있는 상대방에 대한 정보를 나타내는 리스트가 주어집니다. 리스트의 각 요소는 해당 참가자가 선물을 전달할 수 있는 참가자의 인덱스를 표현합니다.
출력 형식
모든 참가자가 선물을 받을 수 있다면 ‘YES’를, 그렇지 않다면 ‘NO’를 출력하시오.
예제 입력
5
1 2 3 4 0
예제 출력
YES
문제 풀이 방법
이 문제는 그래프 이론에서의 “사이클 탐지” 문제와 유사하게 볼 수 있습니다. 각각의 참가자를 노드로, 그들이 선물을 전달할 수 있는 상대방을 간선으로 표현하여 방향 그래프를 구성할 수 있습니다. 모든 노드가 최소한 한 번은 방문될 수 있어야 하며, 그래프가 유일한 사이클을 가질 때 ‘YES’를 반환할 수 있습니다.
단계별 풀이 과정
1. 그래프 구성
주어진 정보를 바탕으로 그래프를 리스트 형태로 구성합니다. 각 참가자가 선물을 전달할 수 있는 상대방을 리스트의 인덱스로 나타냅니다.
2. DFS 혹은 BFS 이용하기
우리는 그래프를 순회하는 방식으로 DFS(깊이 우선 탐색) 또는 BFS(넓이 우선 탐색)을 사용할 수 있습니다. 목표는 모든 참가자가 선물을 받을 수 있는지를 파악하는 것입니다. 즉, 그래프를 순회하며 모든 노드에 방문 여부를 체크합니다.
3. 사이클 탐지
모든 참가자가 서로 선물을 주고받을 수 있도록 사이클이 존재하는지 확인합니다. 이 사이클은 그래프의 각 노드가 반드시 포함되어야 하며, 그 사이클이 하나일 경우 모두가 선물을 받을 수 있습니다.
4. 구현
위의 방법을 바탕으로 파이썬 코드를 구현합니다:
def can_give_gifts(n, connections):
visited = [False] * n
count = 0
def dfs(v):
nonlocal count
visited[v] = True
count += 1
next_giver = connections[v]
if not visited[next_giver]:
dfs(next_giver)
for i in range(n):
if not visited[i]:
count = 0
dfs(i)
if count < n:
return "NO"
return "YES"
# 테스트
n = 5
connections = [1, 2, 3, 4, 0]
print(can_give_gifts(n, connections))
코드 설명
위 코드는 선물 전달을 검증하는 알고리즘입니다. ‘can_give_gifts’ 함수는 참가자 수 n과 선물 전달 가능 리스트 connections를 인자로 받습니다. 각 참가자의 방문 여부를 체크하기 위해 visited 리스트를 설정합니다. DFS를 통해 각 참가자를 방문하면서 카운트를 증가시킵니다. 만약 모든 참가자가 방문되었다면 ‘YES’를, 그렇지 않다면 ‘NO’를 반환합니다.
종합 예제
다음 예제를 통해 이 알고리즘이 실제로 어떻게 작동하는지 살펴봅시다:
6
1 2 3 4 5 0
기대 출력
YES
마무리
이 문제는 파이썬 코딩 테스트에서 빈번히 등장하는 유형입니다. 사이클 탐지를 통해 문제를 해결하는 방법을 익히며, 그래프 개념에 대한 이해를 높이는 데 도움이 됩니다. 다양한 유형의 문제를 풀어보며 알고리즘에 대한 통찰력을 높여보세요.