[코테 유형별로 씹어먹기] BFS 어떤 문제에 사용될까?

개념

---

 

트리나 그래프, 혹은 다른 것들에 대해 탐색을 진행할때 사용하는 방법들이 BFS와 DFS이다. BFS는 한칸씩 이동, DFS는 한쪽으로 이동 대략적으로 이렇게 이해하고 가면 된다. 코테나 대회에서 그래프/트리 문제나 BFS DFS를 응용한 문제들은 꼭 하나씩은 봤던 것 같다.

 

구현

---

# 크기가 N*M인 2차원 행렬 탐색 (가로 M, 세로 N)

from collections import deque

dx=[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):
            nx=x+dx[i]
            ny=y+dy[i]
            if -1<nx<m and -1<ny<n:
                if vi[ny][nx]==0:
                    vi[ny][nx]=1
                    queue.append((nx,ny))

 

나는 2차원 행렬에서 BFS의 경우, 보통 위와 같은 형태로 BFS를 구현한다.

 

예시

---

 

응용될 곳이 정말 많다. 보통 최소 이동 횟수를 구할 때 BFS를 많이 사용한다. 예를 들어 0,0에서 출발해서 N,N까지 가는데 걸리는 시간을 구한다면 만약 장애물같은게 없다면 수학적으로 구하면 되지만 장애물 있다면 BFS로 해결할 수 있다. 이 이동 횟수를 구하는 경우가 보통 트리, 다차원 배열, 그래프, 좌표 이런 곳에 응용되고는 한다.

특히 최단 거리를 요하는 문제의 경우 BFS로 해결해야 하는 경우가 많다.

 

실전

---

 

 

그룹을 만드는 유형이다. 연결된 것들끼리 묶어서 그룹의 개수를 세거나 그룹간의 연결정보를 이용하는 경우

기본

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

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

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

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

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

응용

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

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

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

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

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

 

이런 문제들은 보통 전체 방문 배열을 하나 만들어 놓고, 전체를 확인하면서 방문한 곳은 넘기고 방문하지 않은곳에서 다시 탐색을 시작하면 된다.

 

한 곳에서 출발해서 연결된 것들의 개수를 구하거나 연결된 것들과의 거리 정보를 알아야하는 경우

보통 시작지점이 고정되어있는 문제에서 사용한다.

기본

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

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

응용

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

루트 고정된 혹은 주어지는 트리같은 문제에서 특히 자주 볼 수 있는 유형

 

두 지점 혹은 더 많은 지점 사이의 거리를 구하는 문제

기본

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

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

응용

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

 

 

특정 좌표나 위치에서 시작하여 특정 거리 / 가중치 만큼 이동 가능한 경우

익숙해지면 편하지만 처음에는 햇갈리기 쉬운 유형들

기본

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

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

응용

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

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

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

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

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

BFS를 적용 가능한지 생각하는게 중요한 유형, 숫자가 커진다면 딕셔너리나 압축이 필요할수도 있다.

 

 

지정된 장소들에서 시작해야하는 경우

기본

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

응용

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

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

 

 

나만 이동하는 것이 아닌 다른 것들도 이동하는 경우

기본

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

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

응용

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

풀어본적 없다면 조금 어려울 수도 있다.

 

장애물을 부수는 경우

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

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

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

 

다른 알고리즘과의 응용

시뮬레이션에 응용 / 구현

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

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

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

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

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

보통 골드 중간 정도의 난이도에 자주 등장하는 유형

 

결론

---

그래프 탐색 문제는 전형적인 문제들이 많은 만큼 많이 풀어보는 것이 중요하다,