그래프 탐색(BFS, DFS)에 대한 알고리즘 문제풀이

 

우리가 BFS나 DFS를 사용하는 것은 알아봤다.

응용이 어떻게 될 수 있으며어떤 개념을 알고 가야하는지 고찰해보자.

(대부분 BFS를 요구하고 DFS는 재귀를 이용하는 문제가 많다)

 

---

 

 

우리는 그렇다면 어떤 문제가 DFS고 BFS인지 알 수 있어야 한다.

이 문제를 보자

[프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 1926번 C++ [CPP]

 

 

딱히 BFS인지는 모르겠으나 BFS로 해도 될 것 같은 느낌이 든다.

다음 문제를 보자

 

[프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 2178번 C++ [CPP]

 

최소의 칸 수를 구하란다.

즉, 탈출까지 최단거리를 구하란다.

그래서 BFS를 쓴다.

솔루션을 찾았을 때 BFS는 최단거리를 보장한다.

 

다음 문제를 보자

[프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 7576번 C++ [CPP]

 

 

다음 문제도 봐보자

 

[프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 4179번 C++ [CPP]

 

 

다음

[프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 1697번 C++ [CPP]

 

 

내 말은 저 표현이 있다고 무조건 BFS라는 말은 아니고 저 표현에서 왜 BFS가 생각나야 하는지를 깨달아야 한다는 말이다.

 

BFS는 1단계에서 2단계로 넘어갈 때 같은 레벨의 모든 경우를 거쳐서 간다.

쉽게 말해서 1단계가 4가지가 있다면

1단계 3가지만 하고 2단계를 가는 것이 아니라

4가지를 꼭 다하고 나서야 2단계로 갈 수 있다는 말이다.

그러므로 우리는 만약 솔루션을 발견했을 때 해당 단계가 최소 단계임을 알 수 있는 것이다.

그게 최단거리, 최소시간 등으로 표현될 뿐이다.

 

다른 문제도 보자.

 

 

---

그렇다면 BFS, DFS 문제를 풀 때 자신에게 꼭 물어보고 지나가야하는 몇가지 질문이 있다.

 

1. 입력이 어떻게 주어졌는가?

-> 문자열일 경우 일반적인 cin으로 하면 문자열 자체를 받는 것을 알고 있을 것

 

2. 이전 상태가 내가 할 탐색에 영향을 주는가?

-> ex)  방문 전, 방문 중(현재 노드), 방문 후

-> ex) 벽, 중복 방문 x, 상대방의 위치 등등..

 

3. 이동을 어떻게 하는가?

-> 일반적으로 왼쪽, 위쪽, 오른쪽, 아래쪽으로 이동가능하지만 대각선으로도 이동 가능한 때도 있고 다양하다.

 

4. 탐색에 대한 조건이 있느냐?

-> 벽에 닿는다면 반대쪽 벽으로 넘어간다는 등.. 여러가지 존재

-> 이 때는 탐색할 수 없는 경우라든가 이 때는 무엇인가 갱신해야한다든지 등이 있다.

 

 

---

 

 

 

일반적으로 BFS는 최단경로 또는 위상정렬에 쓰인다.

일반적으로 DFS는 백트래킹, 사이클 찾기, 위상정렬에 쓰인다.