[Python] 24444번 알고리즘 수업 - 너비 우선 탐색 1

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

 

은근 까다롭던데 정답 비율이 46.422%라니... 믿을 수 없다...

아직 그냥 내가 허접인걸로,,,,

 

 

import sys
input=sys.stdin.readline

#3.함수 정의
def bfs(V,E,R): # V : 정점 집합, E : 간선 집합, R : 시작 정점
    #ans=[]
    queue=[R]
    visited[R]=True
    res=[0 for _ in range(N+1)]
    cnt=0

    while queue:
        node=queue.pop(0)
        #ans.append(node)
        cnt+=1
        res[node]=cnt

        for next_node in graph[node]:
            if not visited[next_node]:
                queue.append(next_node)
                visited[next_node]=True

    for i in range(1,N+1):
        print(res[i])

#1.입력 받기
N,M,R=map(int,input().split()) #정점,간선,시작 정점
graph=[[] for _ in range(N+1)]
for _ in range(M):
    u,v=map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)
#그래프 오름차순으로 정렬
for i in range(1,N+1):
    graph[i]=sorted(graph[i])
visited=[False for _ in range(N+1)]
#[[], [2, 4], [1, 3, 4], [2, 4], [1, 2, 3], []]

#4.출력
bfs(visited,graph,R)