[알고리즘/백준] 2644번 촌수계산

2644번 촌수계산 - https://www.acmicpc.net/problem/2644

( 개인적으로 BFS로 푸는 코드를 생각하기까지 어려웠음 😥 )

 

 

접근 방법

 

처음에는 BFS_DFS 문제라고 생각하지 못했다. 그래프 문제인 것은 알았는데 조금 복잡하게 구현했다.

- 그래프를 dictionary로 만들었다.

- num1의 부모 노드를 num1_list에 모두 담아주고 루트노드일 때 멈춘다.

- num2도 num1과 마찬가지로 진행하되 num1_list에 들어있는 노드가 나오게 되면 index로 촌수를 계산해준다.

 

def relatives(graph, num1, num2):
    result = -1
    num1_list = [num1]
    num2_list = [num2]
    while num1 in graph.keys():
        num1 = graph[num1]
        num1_list.append(num1)

    if num2 in num1_list:
        return num2_list.index(num2) + num1_list.index(num2)

    while num2 in graph.keys():
        num2 = graph[num2]
        num2_list.append(num2)
        if num2 in num1_list:
            result = num2_list.index(num2) + num1_list.index(num2)
            break

    return result


n = int(input()) #전체 사람의 수
num1, num2 = map(int, input().split()) # 촌수를 계산해야 하는 서로 다른 두 사람의 번호

m = int(input()) #부모 자식든 간의 관계의 개수
graph = {}

for i in range(m):
    node1, node2 = map(int, input().split())
    graph[node2] = node1

print(relatives(graph, num1, num2))

 

제출 후 다른 사람들의 풀이를 찾아보니 BFS 또는 DFS를 많이 사용하는데 대부분 BFS로 탐색하여 찾았다.

코드를 짜려고 보니 루트노드가 제공되지 않는데 탐색을 어디부터 할 것인지부터 막막했고

num1이나 num2에서 시작하게 되면 부모와 자식 모두를 탐색해야 하는데 그러한 방법이 잘 생각나지 않았다.

그래서 검색해서 다른 분들의 코드를 참고하여 이해한 후 다시 짜보았다.

 

- BFS 활용

- graph를 중첩 list로 만들어준다. 이때 부모 노드와 자식 노드를 구분하지 않고 넣어준다.

 

for i in range(m):
    node1, node2 = map(int, input().split())
    graph[node2-1].append(node1)
    graph[node1-1].append(node2)

 

- relatives_bfs 함수에서 visited list를 만들었다.

이를 활용하여 num1부터 탐색을 시작하고 부모와 자식 상관없이 촌수를 올바르게 계산할 수 있다.

queue에 popleft한 node의 부모 노드와 자식 노드를 모두 넣는다. 이때 조건은 방문하지 않은 노드이다.

그리고 그 노드를 넣을 때 visited list에 visited[node]+1을 넣어 촌수를 계산하여 준다.

만약 그 노드가 num2라면 visited[node]+1을 반환한다. 다 돌았을 때도 찾지 못하면 -1을 반환한다.

 

최종 제출 코드

 

#BFS

from collections import deque

def relatives_bfs(graph, num1, num2):
    visited = [0] * (n+1)
    queue = deque([num1])
    while queue:
        node = queue.popleft()
        for i in graph[node-1]:
            if visited[i] == 0:
                queue.append(i)
                visited[i] = 1 + visited[node]
                if i == num2:
                    return visited[num2]
    return -1


n = int(input()) #전체 사람의 수
num1, num2 = map(int, input().split()) # 촌수를 계산해야 하는 서로 다른 두 사람의 번호

m = int(input()) #부모 자식든 간의 관계의 개수
graph = [[] * n for i in range(n)]

for i in range(m):
    node1, node2 = map(int, input().split())
    graph[node2-1].append(node1)
    graph[node1-1].append(node2)

print(relatives_bfs(graph, num1, num2))