내 인생 이대로 ㅈ될 수 없다

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

내 풀이

import sys
from collections import deque

input = sys.stdin.readline

def solution():
    ans=[]
    
    n,m = map(int,input().split())
    graph=[[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    
    def bfs(v):
        q = deque([v])
        visited[v]=1
        print('q=',q)

        while q:
            node = q.popleft()
            print('node=',node)

            for i in graph[node]:
                print('i=',i)
                if not visited[i]:
                    visited[i] = visited[node] + 1
                    q.append(i)
        print('visited=',visited)

    for i in range(1,n+1):
        visited=[0]*(n+1)
        bfs(i)
        ans.append(sum(visited))

    for i in range(len(ans)):
        if ans[i]==min(ans):
            print(i+1)
            return

solution()

5 5
1 3
1 4
4 5
4 3
3 2
q= deque([1])
node= 1
i= 3
i= 4
node= 3
i= 1
i= 4
i= 2
node= 4
i= 1
i= 5
i= 3
node= 2
i= 3
node= 5
i= 4
visited= [0, 1, 3, 2, 2, 3]
q= deque([2])
node= 2
i= 3
node= 3
i= 1
i= 4
i= 2
node= 1
i= 3
i= 4
node= 4
i= 1
i= 5
i= 3
node= 5
i= 4
visited= [0, 3, 1, 2, 3, 4]
q= deque([3])
node= 3
i= 1
i= 4
i= 2
node= 1
i= 3
i= 4
node= 4
i= 1
i= 5
i= 3
node= 2
i= 3
node= 5
i= 4
visited= [0, 2, 2, 1, 2, 3]
q= deque([4])
node= 4
i= 1
i= 5
i= 3
node= 1
i= 3
i= 4
node= 5
i= 4
node= 3
i= 1
i= 4
i= 2
node= 2
i= 3
visited= [0, 2, 3, 2, 1, 2]
q= deque([5])
node= 5
i= 4
node= 4
i= 1
i= 5
i= 3
node= 1
i= 3
i= 4
node= 3
i= 1
i= 4
i= 2
node= 2
i= 3
visited= [0, 3, 4, 3, 2, 1]
3

개인적으로 이 문제 bfs 공부하기 굉장히 좋은 문제라고 생각한다.

하여 좀 귀찮지만 모든 로그를 찍어보기 위하여 위와 같이 결과 값도 첨부한다

bfs의 가장 큰 특징은 가까운 정점부터 방문한다는 것이다.

위 문제에서 최초 1이 들어가게되면 

visited의 형태는 = [0,1,0,0,0,0] 

graph = [[],[3,4],[3],[1,4,2],[4]] 

이런식일 테다.

bfs 를 풀때마다 최초에 visited에 1을 넣는것이 좀 의아했었다. 근데 이렇게 로그로 찍어보니까 어차피 모든 visited에 1을 더해주니까 결과값에는 영향이 없다는것을 눈으로 확인 할 수 있었다.

다른사람의 풀이