2644번: 촌수계산

 

 

 

풀이

 

dfs와 bfs로 풀 수 있는 문제입니다.

 

dfs

...

촌수를 계산해야 하는 서로 다른 두 사람의 번호를 per1, per2로 입력 받고 dfs에 per1을 값으로 삽입하고 호출합니다.

 

반복문을 돌리면서 graph[v]의 값을 i로 하나씩 빼온뒤 방문하지 않은 곳이라면 visited[i]의 값을 visited[v]+1한 값으로 변경 해서 방문처리를 해주고 dfs를 재호출합니다.

 

함수가 종료된뒤 visited[per2]의 값이 0을 초과한다면 visited[per2]의 값을 출력하고 그렇지 않다면 -1를 출력합니다. 

...

 

 

bfs

...

촌수를 계산해야 하는 서로 다른 두 사람의 번호를 per1, per2로 입력 받고 bfs에 per1을 값으로 삽입하고 호출합니다.

 

반복문을 돌리면서 graph[v]의 값을 i로 하나씩 빼온뒤 방문하지 않은 곳이라면 visited[i]의 값을 visited[v]+1한 값으로 변경 해서 방문처리를 해주고 queue에 i를 삽입합니다.

 

함수가 종료된뒤 visited[per2]의 값이 0을 초과한다면 visited[per2]의 값을 출력하고 그렇지 않다면 -1를 출력합니다. 

...

 

 

 

파이썬 dfs

import sys
sys.setrecursionlimit(1000000)

def dfs(v):
    for i in graph[v]:
        if visited[i] == 0:
            visited[i] = visited[v]+1
            dfs(i)
            
n = int(input())
per1, per2  = map(int, input().split())
m = int(input())

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

for _ in range(m):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)
    graph[end].append(start)

dfs(per1)
print(visited[per2] if visited[per2] > 0 else -1)

 

 

 

파이썬 bfs

from collections import deque
import sys

def bfs(v):
    queue = deque()
    queue.append(v)
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if visited[i] == 0:
                visited[i] = visited[v]+1
                queue.append(i)
            
n = int(input())
per1, per2  = map(int, input().split())
m = int(input())

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

for _ in range(m):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)
    graph[end].append(start)

bfs(per1)
print(visited[per2] if visited[per2] > 0 else -1)