[실전 알고리즘] 0x05강 - BFS, DFS_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x09강 - BFS, [실전 알고리즘] 0x0A강 - DFS에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

이번 시간엔 코딩테스트 단골 유형인 BFS, DFS에 대해 알아보겠습니다.

 

 

시작하기에 앞서, 원래는 0x03장에서 언급했던 전위 중위 후위 표기식을 먼저 다루려고 했습니다. 해당 내용은 학부 자료구조에서 스택을 배울 때 거의 대부분 짚고 넘어가는 내용이기 때문입니다. 그러나 표기식이 난이도도 어렵고 요구되는 구현력도 다소 높은 것에 비해 다소 지엽적인 내용이기 때문에 코딩 테스트와 면접에 나올 확률은 0에 가깝다고 판단, 이 내용을 실전 알고리즘 강의에서 다루지 않기로 결정했습니다.

 

그러나 삼성 역량 테스트 B형 정도의 수준에는 충분히 나올 수 있는 내용이니 본인이 알고리즘을 더 깊게 공부하고 싶다면 여유가 있을 때 직접 찾아서 공부를 해보세요.

 

플러드필은 다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘입니다. 마치 그림판에서 색 채우기 명령으로 동일한 색을 전부 바꿔버리는 것과 동일합니다.

 

플러드 필 문제는 DFS/BFS 알고리즘으로 해결할 수 있습니다. 플러드 필은 적당한 난이도의 자료구조 지식과 구현력을 요구하는 문제이기 때문에 코딩테스트에 정말 자주 나오는 유형입니다. BFS는 큐로 구현할 수 있고 DFS는 스택으로 구현할 수 있습니다.

 

BFS는 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘입니다. 너비라니.. 잘 이해가 안가시죠? 정상입니다. 원래 BFS와 DFS는 그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘으로, 다차원 배열이 그래프 자료구조의 특수한 형태이기 때문에 다차원 배열에서도 BFS, DFS를 사용할 수 있는 것입니다.

 

그렇기에 BFS와 DFS를 정확하게 이해하려면 그래프 자료구조에 대한 이해가 선행되어야 하나 그건 배보다 배꼽이 커지는 느낌입니다. 대신 구체적인 알고리즘을 보면서 다차원 배열에서의 BFS를 이해해봅시다.

 

BFS 과정을 글로 풀어적으면 간단합니다.

 

이 과정에서 모든 칸이 큐에 1번씩만 들어감이 보장되므로 시간복잡도는 칸이 $N$개일 때 $O(N)$입니다. 직접 예시를 보면서 이해해봅시다.

 

(0, 0)에서 시작합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

예시가 잘 이해가시나요?

 

BFS를 실제로 구현하기 위해 큐에 int 2개를 묶은 원소가 들어가야 합니다. 이 부분을 처리하기 위해 STL의 pair를 활용했습니다. 구현 코드를 확인해보세요. 

 

현재 코드는 BFS 알고리즘으로 Flood Fill을 수행할 수 있습니다. 이외에 BFS를 응용할 수 있는 부분들에 대해 알아보겠습니다. 첫 번째 문제는 BOJ 1926번: 그림입니다. 이 문제를 풀기 위해서는 (0, 0)에서 시작해 BFS를 돌고 끝나는 것이 아니라 이중 for문을 돌면서 아직 방문하지 않은 시작점들을 계속 찾아서 Flood Fill을 수행해야 합니다. 그리고 넓이를 구하기 위해서는 각 시작점에 내부적인 변수를 두어 큐에서 원소를 꺼낼 때 마다 그 변수를 1 증가시키면 됩니다. 정답 코드를 확인해보세요.

 

두 번째 문제는 BOJ 2178번 : 미로 탐색입니다. 이 문제는 미로의 좌측 상단이 시작점이고 우측 하단이 끝점일 때 시작점에서 끝점으로 가는 최단 경로의 길이를 찾는 문제입니다. 놀랍게도 BFS를 이용해 시작점에서 연결된 다른 모든 점으로의 최단 경로를 찾을 수 있습니다. 이 성질을 이해하기 위해 BFS의 과정을 다시 살펴봅시다.

 

뭔가 시작점 (0, 0)에서부터 퍼져나가는 느낌이 들지 않나요? (0, 0)에서부터의 거리를 적어보면 더욱 명확해집니다. 현재 보는 칸으로부터 추가되는 인접한 칸은 반드시 현재 보는 칸 보다 시작점으로부터 1만큼 더 떨어져 있습니다.

 

이 강의에서 해당 성질을 증명하지는 않지만, 귀납법으로 증명이 가능합니다. 이제 이 성질을 이용해 시작 점과의 거리를 계산할 dist 배열을 하나 둠으로서 시작 점에서 다른 모든 점으로 가는데 필요한 거리를 계산할 수 있습니다.

 

dist 배열을 미리 -1로 초기화 시켜두면 굳이 vis 배열을 따로 둘 필요 없이 dist 배열의 값이 0 이상인지를 가지고 방문 여부를 확인할 수 있습니다.(정답 코드)

 

BFS의 구현에서 실수를 할 여지가 굉장히 많습니다. 코드를 직접 짜봤는데 답이 나오지 않을 경우에는 이런 상황들을 확인해보세요.

 

두 번째로 살펴볼 알고리즘은 DFS입니다. DFS는 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘입니다. BFS처럼 이해가 안가는건 똑같네요. BFS와 흐름은 거의 동일하나 큐 대신 스택을 쓴다는 차이점만 있습니다. 역시 구체적인 알고리즘을 보면서 다차원 배열에서의 DFS를 이해해봅시다.

 

보다시피 BFS와 DFS는 큐에서 원소를 넣었다가 꺼내는지, 스택에서 원소를 넣었다가 꺼내는지에 대한 차이밖에 없습니다. 다시 한 번 직접 예시를 보면서 이해해봅시다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

마찬가지로 STL의 pair를 이용해 작성된 예시 코드입니다. 단 출력되는 방문 순서는 상/하/좌/우 중 어디를 먼저 스택에 넣냐에 따라 다를 수 있습니다. (2019-01-06에 두두님이 오류를 알려주셔서 수정했습니다. 감사합니다!)

 

BFS와는 다르게 DFS에서는 현재 보는 칸으로부터 추가되는 인접한 칸은 현재 보는 칸 보다 시작점으로부터 1만큼 더 떨어져있다는 성질이 성립되지 않습니다. 그렇기 때문에 시작점으로부터의 거리를 잴 때는 DFS 대신 BFS를 사용해야 합니다.

 

그렇기에 다차원 배열에서 DFS는 딱히 쓸 일이 없습니다. 어차피 Flood Fill은 BFS에서도 할 수 있고, DFS에서는 시작 점에서 다른 모든 점으로의 거리를 잴 수 없기 때문입니다. 그러나 나중에 그래프를 배우고 난 뒤에 DFS를 사용해야 하는 상황이 생기므로 DFS에 대한 개념은 가지고 있는 것이 좋습니다.

 

Flood FIll / BFS / DFS 관련 문제는 코딩테스트 뿐만 아니라 정보올림피아드에서도 워낙 자주 나오는 유형이라 BOJ에 정말 끝도 없이 쌓여 있습니다. 그 중에서 그래프 개념이 필요없는 문제들을 뽑아 그룹에 난이도 순으로 담아두었으니 꾸준하게 풀어보세요.

 

코딩테스트에 단골로 출제되는 유형이기 때문에 반복 숙달을 통해 코드의 흐름을 손에 익히는 것이 중요합니다.

 

이번 강의에서 Flood Fill / BFS / DFS를 익혔고, BFS의 응용 사례들과 자주 실수하는 부분을 살펴보았습니다.