[백준] 1389번 파이썬

문제: https://www.acmicpc.net/problem/1389

문제 해결 방법

1. 문제 지문이 꽤 길지만, 데이터간의 관계를 살펴보면 그래프 탐색 문제다.
2. 나는 BFS 탐색으로 문제를 해결했는데 핵심 부분은 바로 25번째 라인이다. 시작 노드를 트리 자료구조의 뿌리 노드라고 잡고 트리형태로 탐색을 하면, 같은 레벨에 있는 노드를 전부 탐색할때까지 반복문을 돌린다
3. 그 뒤 path를 1씩 늘려주면, 트리의 레벨이 내려감에 따라 path역시 1개씩 증가한다.
4. 비슷한 문제로 백준 24447번 문제가 있다.

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

N, M = map(int, input().split())
GRAPH = [[] for _ in range(N)]

# 그래프의 인덱스는 1부터 시작하기에 들어오는 값들을 -1 계산해서 넣기
for m in range(M):
    start, end = map(int, input().split())
    GRAPH[start-1].append(end-1)
    GRAPH[end-1].append(start-1)


# bfs 탐색으로 순차적으로 목표 노드까지의 path를 구함
def bfs(start, end):
    queue = deque()
    queue.append(GRAPH[start])
    path = 0

    while queue:
        path += 1
        # 순차적으로 같은 레벨에 있는 노드를 방문해야 한다.
        # 따라서 처음 같은 레벨에 있는 노드의 정보만큼 edge를 탐색해야됨.
        for _ in range(len(queue)):
            edges = queue.popleft()

            for edge in edges:
                if not visit[edge]:
                    visit[edge] = True
                    if edge == end:
                        return path
                    else:
                        queue.append(GRAPH[edge])


# 탐색 시작
answer = []
for i in range(N):
    temp = 0
    for j in range(N):
        if i == j:
            continue
        else:
            visit = [False] * N
            temp += bfs(i, j)
    answer.append(temp)


# 정답 출력
minimum = min(answer)
for i in range(N):
    if answer[i] == minimum:
        print(i+1)
        break