99클럽 코테 스터디 5일차 TIL: 너비 우선 탐색

오늘의 문제 | 24444. 알고리즘 수업 - 너비 우선 탐색 1

이번에는 어제와 달리 BFS문제이다. 똑같은 형식이기에 비슷한 문제가 있을 것이라는건 파악하고 시작했다. 이번에도 수도코드를 보고 코드를 똑같이 구현하면 큰 문제없이 되지 않을까 생각중이다.

 

작성하면서 느낀건, BFS는 재귀함수로 작성하지 않아도 되기에 굳이 recursionlimit을 늘릴 필요가 없다. 단지 입력 횟수만 많다는것만 고려하면 오늘은 어렵지 않게 풀 수 있었다.

import sys
from collections import deque
input=sys.stdin.readline
sys.setrecursionlimit(100_000)

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

graph=[[] for i in range(n+1)]
visit=[0 for i in range(n+1)]
idx=1

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

for i in range(1,n+1):
    graph[i].sort()

def bfs(graph, start):
    global idx
    visit[start]=idx
    idx+=1

    deq=deque()
    deq.append(start)

    while deq:
        node=deq.popleft()
        for i in graph[node]:
            if visit[i]==0:
                visit[i]=idx
                idx+=1
                deq.append(i)
bfs(graph,r)
print(*visit[1:],sep="\\n")

오늘의 회고

오늘은 솔직히 여태 했던 문제 중에 가장 쉬운 편이었다. 별다른 생각없이 코드만 구현했는데도 문제 없이 바로 정답을 맞았다. BFS를 오랜만에 하다보니 두려운 부분도 있었지만 생각보다 그래프 구현이 그리 어려운 코드가 아니며, 아직 나도 잘 기억하고 있다는 생각이 들었다.

앞으로도 그래프 구현은 꾸준히 해야 실력을 유지할 수 있지 않을까 싶다.