[BFS] 2644 촌수 계산

2644번: 촌수계산

첫 번째 시도

# 부모와 자식 : 1촌
# 사람들은 1, 2, 3, ... , n (1 <= n <= 100)의 연속된 번호로 각각 표시된다.

import sys
input = sys.stdin.readline
from collections import deque as dq

def bfs(graph, start, destination, visited):
    global ans
    queue = dq([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        ans += 1
        for i in graph[v]:
            if i == destination:
                return ans
            if not visited[i]:
                queue.append(i)
                visited[i] = True
    return -1

# 입력: 전체 사람 수 n
n = int(input())
# 기본 변수:
graph = []
for i in range(n+1):
    graph.append([])
visited = [False] * (n+1)
ans = 0
start = 0
# 입력: 촌수를 계산할 서로 다른 두 사람의 번호가 주어진다.
start, destination = map(int, input().split())
# 입력: 부모 자식들 간의 관계의 개수 m
m = int(input())
# 입력: 부모, 자식 관계
for _ in range(m):
    parent, child = map(int, input().split())
    graph[parent].append(child)
    graph[child].append(parent)
print(bfs(graph, start, destination, visited))

 

두 번째 시도

개선점 : ans로 노드 간 거리를 측정하기보다, visited 배열에 누적 카운트를 넣기

# 부모와 자식 : 1촌
# 사람들은 1, 2, 3, ... , n (1 <= n <= 100)의 연속된 번호로 각각 표시된다.

import sys
input = sys.stdin.readline
from collections import deque as dq

def bfs(graph, start, destination, visited):
    global ans
    queue = dq([start])
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] += visited[v]+1

# 입력: 전체 사람 수 n
n = int(input())
# 기본 변수:
graph = [[] for i in range(n+1)]
visited = [0] * (n+1)
# 입력: 촌수를 계산할 서로 다른 두 사람의 번호가 주어진다.
start, destination = map(int, input().split())
# 입력: 부모 자식들 간의 관계의 개수 m
m = int(input())
# 입력: 부모, 자식 관계
for _ in range(m):
    parent, child = map(int, input().split())
    graph[parent].append(child)
    graph[child].append(parent)
bfs(graph, start, destination, visited)
print(visited[destination] if visited[destination] > 0 else -1)

 

다음엔 DFS로 풀어봐야겠다.