백준 - 1389

문제 설명

사람들의 관계에서, 몇 번 다리를 건너야 모두 알 수 있는지를 확인하고, 그 중 인덱스가 작은 사람을 결과로서 출력하는 문제다.

접근 방법

1. 그래프 이론을 떠올려, 각 사람들의 관계를 리스트로서 표현
2. 첫 번째 사람부터 방문하여 관계가 있는 사람들을 먼저 방문
3. 관계가 있는 사람들의 관계를 이용하여 갈 수 있는 사람들 방문
   (싸이월드 파도타기 같은 개념)
4. 2~3번을 반복하여 거리 측정
5. 모든 사람 반복한 후, result에 저장된 값들 중 작은 인덱스 출력

작성한 코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())

relation = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())

    relation[a].append(b)
    relation[b].append(a)

result = []

for i in range(1, n+1):
    num = [0] * (n+1)
    visit = [i]
    queue = deque()		# deque 활용
    queue.append(i)

    while queue:
        idx = queue.popleft()
        for i in relation[idx]:
            if i not in visit:
                num[i] = num[idx] + 1
                visit.append(i)		# visit 방문 처리
                queue.append(i)		# queue에 넣기
    result.append(sum(num))

print(result.index(min(result))+1)

예) 1번 예시

코드로 디버깅 과정을 보이면 위와 같다.

순차적으로 BFS를 수행하며 모든 노드를 방문한다.