[Python/코테] 백준 2644 촌수 계산 | 무방향 그래프 구현하기

2644 촌수 계산

문제 및 조건 설명: https://www.acmicpc.net/problem/2644

알고리즘 설계

💡idea.

• 입력값에 따라 트리를 만들고, 노드 간의 거리를 구하는 것으로 간단하게 이해할 수 있다. (왼쪽 사진 참고)
• 깊이 우선 탐색인 DFS를 사용한다. BFS를 사용할 수도 있다. 

 

🎲step.

1. 입력 값을 이차원 배열에 저장하여 그래프 구조를 구현한다.
2. 시작 노드에서 출발하여 연결된 노드를 탐색하는 DFS를 진행한다. 방문 표시(거리 계산)할 리스트를 만들고 시작 노드를 0으로 초기화한다.
3. 두번째 노드에 도착하면, 시작 노드에 1을 더해 거리가 1임을 표시한다.
   세번째 노드에 도착하면, 직전 노드에 1을 더해 시작 노드로부터의 거리를 표시한다.
4. 최종적으로 찾기 원하는 노드의 값을 출력한다.

알고리즘 구현

import sys
from collections import deque

n = int(input())
start, end = map(int, input().split())
k = int(input())

family = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(k):
    input = sys.stdin.readline().split()
    # 무방향 그래프
    family[int(input[0])].append(int(input[1]))
    family[int(input[1])].append(int(input[0]))


def dfs(start):
    stack = deque()
    stack.append(start)
    visited[start] = 0

    while stack:
        node = stack.pop()

        for next in family[node]:
            if not visited[next]:
                visited[next] = visited[node] + 1
                if next == end:
                    break
                else:
                    stack.append(next)


result = dfs(start)

if visited[end] > 0:
    print(visited[end])
else:
    print(-1)

나다어

• 두 노드 사이의 거리를 구하기 위해서 깊이 우선 탐색을 사용했다. DFS는 스택을 사용한다.
• 거리를 구할 때는 노드에 도착할 때마다 기존 노드+1을 해주는 것으로 구현 가능하다.

파이썬에서 그래프 자료 구조 구현하기

 

무방향 그래프와 방향 그래프 두 가지가 있지만, 기본적이고 문제에서 사용되었던 무방향 그래프에 대해서만 확인해보자.

 

그래프는 왼쪽과 같이 인접 행렬로 표현할 수 있다. 각 정점 i와 j가 간선으로 연결되어 있으면 matrix[i][j] = 1, 아니면 0의 값을 가진다.

이 인접행렬을 사전 혹은 인접리스트로 구현할 수 있다. 사전일 때는 키값이 곧 정점의 값이 되고, 배열로 구현하면 인덱스가 정점의 값이 된다.

• 배열의 크기는 정점의 수와 같다.
• 배열의 각 인덱스는 그래프의 특정 정점을 나타낸다.
• 배열의 인덱스 i에 있는 값은 정점 i에 인접한 모든 정점을 포함하는 배열이다.
  예를 들어, graph[0] 은 정점 0 에 연결된(이웃) 모든 노드를 갖는다.

예시로, 왼쪽의 그래프를 리스트로 구현하면 아래와 같다.

graph1 = [[], [2,3,5], [1,3], [1,2,4], [3,5], [1,4]] # 그림의 숫자를 맞추기 위해 0인덱스는 비워뒀다.

 

출처: https://wikidocs.net/196182

https://www.geeksforgeeks.org/graph-and-its-representations/