[BOJ] 백준 2644 촌수계산 / BFS, DFS

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 풀이 과정

 

 

탐색 문제로서 BFS와 DFS 두 가지 방법 모두 가능한 문제이다.

 

입력으로 주어진 연결 관계를 2차원 리스트로 양 쪽 모두에 저장한다.

 

visited 리스트에는 출발점에서 해당 번호의 노드까지 이동하는 거리(촌수)를 저장한다.

 

visited의 도착점 위치 값이 0이면 가족 관계가 전혀 없다는 뜻이므로 -1을 출력하고,

값이 존재한다면 그 촌 수를 출력한다.

 

 

작성언어: Python

 

 

BFS

 

from sys import stdin
from collections import deque


n = int(stdin.readline().rstrip())
man1, man2 = map(int, stdin.readline().rstrip().split())
m = int(stdin.readline().rstrip())
family_tree = [[] for _ in range(n+1)]    # 가족 관계
visited = [0]*(n+1)    # 방문 처리
queue = deque()

# 가족 관계 정보 입력
for _ in range(m):
    x, y = map(int, stdin.readline().rstrip().split())
    family_tree[x].append(y)
    family_tree[y].append(x)
   

# BFS 수행
queue.append(man1)
while queue:
    now = queue.popleft()
    for man in family_tree[now]:
        # 아직 탐색하지 않은 노드이면서, 시작노드가 아니면 큐에 삽입
        if man != man1 and visited[man] == 0:
            # 촌수 1 증가
            visited[man] = visited[now] + 1
            queue.append(man)

# 탐색 후에도 여전히 0이라면 친척 관계가 전혀 없다는 것(연결되어있지 않음)
if visited[man2] == 0:
    print(-1)
else:
    print(visited[man2])

 

 

DFS

 

from sys import stdin


n = int(stdin.readline().rstrip())
man1, man2 = map(int, stdin.readline().rstrip().split())
m = int(stdin.readline().rstrip())
family_tree = [[] for _ in range(n+1)]    # 가족 관계
visited = [0]*(n+1)    # 방문 처리

# 가족 관계 정보 입력
for _ in range(m):
    x, y = map(int, stdin.readline().rstrip().split())
    family_tree[x].append(y)
    family_tree[y].append(x)


# DFS 수행
def dfs(before):
    global family_tree, visited, man1
    for man in family_tree[before]:
        if man != man1 and visited[man] == 0:
            visited[man] = visited[before] + 1
            dfs(man)


dfs(man1)
    
# 탐색 후에도 여전히 0이라면 친척 관계가 전혀 없다는 것(연결되어있지 않음)
if visited[man2] == 0:
    print(-1)
else:
    print(visited[man2])