[코테 유형별로 씹어먹기] BFS 어떤 문제에 사용될까?
개념 트리나 그래프, 혹은 다른 것들에 대해 탐색을 진행할때 사용하는 방법들이 BFS와 DFS이다. BFS는 한칸씩 이동, DFS는 한쪽으로 이동 대략적으로 이렇게 이해하고 가면 된다. 코테나 대회에서 그래프/트리 문제나 BFS DFS를 응용한 문제들은 꼭 하나씩은 봤던 것 같다. 구현# 크기가 N*M인 2차원 행렬 탐색 (가로 M, 세로 N)from collections import dequedx=[1,-1,0,0]dy=[0,0,-1,1]def bfs(X,Y): vi=[[0]*M for i in range(N)] queue=deque([(X,Y)]) vi[Y][X]=1 while queue: x,y=queue.popleft() for i in range(n): ..