[BOJ] Python 백준 알고리즘 수업 - 너비 우선 탐색 1(24444)

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

 

 

전형적인 bfs의 문제 

방문 순서를 지정하는 것이므로, 고유한 값으로 visited를 갱신해야함

cnt를 전역으로 선언해서 bfs에 방문이 될 때 마다 cnt 값을 증가시켜 값을 갱신

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

N, M, R = map(int,input().split())
s = [[] for _ in range(N+1)]
visited = [0] * (N+1)
cnt = 1

def bfs(v):
    global cnt
    queue = deque()
    queue.append(v)
    visited[v] = cnt

    while queue:
        x = queue.popleft()
        s[x].sort()
        for i in s[x]:
            if visited[i] == 0:
                cnt += 1
                visited[i] = cnt
                queue.append(i)


for _ in range(M):

    u,v = map(int,input().split())
    s[u].append(v)
    s[v].append(u)

bfs(R)

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

 

 

회고.

이미 아는 것을 풀어 기억하고 있는 상태에서 코드를 치는거라 바로 풀수 있었다.

2주 뒤에 꼭 다시 풀어봐야 겠다,,