촌수계산

항해 TIL

www.acmicpc.net

https://www.acmicpc.net/problem/2644

아래 그래프 문제는 인접 리스트 기반으로 구현이 됩니다

먼저 주어진 입력을 인접 리스트 기반 그래프로 구현합니다

촌수 문제는 시작 노드(사람)으로부터 몇 번의 노드를 거쳐 사람(노드)과 연결되는지를 파악하는 문제입니다.

따라서 깊이우선탐색을 통해 몇 번의 노드를 거쳐 정답 노드로 갈 수 있는지 파악해보겠습니다

아래 문제에서 dfs의 back tracking 조건은 정답인 y를 만났을 때입니다.

보통 dfs는 입력 받은 리스트의 크기 혹은 그래프의 길이를 재귀 호출 종료 조건을 걸곤 하는데, 아래 문제는 인접 리스트 기반이고, 시작 노드에서 출발 후, 끝이 정해져 있기 때문에 스택이 무한대로 쌓일 일이 없습니다.

따라서 if cnt == n + 1: 조건은 불필요합니다. (불안하면 넣는 정도..?)

n = int(input())

x, y = map(int, input().split())

m = int(input())

graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    # 촌은 양방향 연결이기 때문에 각각 노드에 할당
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (n + 1)

# print(graph)
ans = 0
# 사용하지 않지만, 노드 탐색을 디버깅하기 위해 만든 path 리스트
# path = []

def dfs(x, cnt):
    global ans

    visited[x] = True
    # print(path)
    if x == y:
        ans = cnt
        # print('sss', path)
        return

    if cnt == n + 1:
        # print(path)
        return

    # 그래프에 연결된 노드 탐색
    for i in graph[x]:
        # 연결된 노드 중 방문하지 않는 노드가 있다면
        if not visited[i]:
            # path.append(i)
            # 방문
            dfs(i, cnt + 1)
            # path.pop()

dfs(x, 0)

if ans == 0:
    print(-1)
else:
    print(ans)
Python
복사