[Python] 백준 2644번 촌수계산

문제

2644번: 촌수계산

입력

• 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.
• 각 사람의 부모는 최대 한 명만 주어진다.

출력

• 입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

입력 예제

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

9
8 6
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

출력 예제

3

-1

문제 풀이

• 경로가 1인 최단거리를 구하는 문제로 볼 수 있어 다익스트라 알고리즘을 사용하여 풀이하였다.
• 입력받은 노드들간의 거리비용을 1로하여 그래프에 삽입한 후, (비용, 노드번호)를 힙에 넣고 최단거리를 구한 후, 구하려는 x값에서 출발해 y까지의 최단 거리를 구한 후 출력한다.
• 정석풀이는 DFS 알고리즘을 사용하는 것이었고, 다익스트라와 BFS알고리즘을 사용하여 풀이했을 때와 비교해서 제일 효율적이었다.

다익스트라 코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n = int(input())
x,y = map(int,input().split())
m = int(input())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append((b,1))
    graph[b].append((a,1))

def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))
dijkstra(x)
if distance[y] == INF:
    print(-1)
else:
    print(distance[y])

DFS 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
INF = int(1e9)
n = int(input())
x,y = map(int,input().split())
m = int(input())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

result = 0
def dfs(v,cnt):
    global result
    visited[v] = True
    cnt += 1
    if v == y:
        result = cnt
    for i in graph[v]:
        if not visited[i]:
            dfs(i,cnt)

dfs(x,0)
if result == 0:
    print(-1)
else:
    print(result - 1)

BFS 코드

from collections import deque
import sys
input = sys.stdin.readline
INF = int(1e9)
n = int(input())
x,y = map(int,input().split())
m = int(input())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

result = 0
def bfs(v):
    queue = deque()
    queue.append(v)
    visited[v] = 0
    while queue:
        now = queue.popleft()
        for i in graph[now]:
            if not visited[i]:
                visited[i] = visited[now] + 1
                queue.append(i)
bfs(x)
if not visited[y]:
    print(-1)
else:
    print(visited[y])