[c++] 백준 미로탐색(2178), BFS

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

 

• 위와 같은 미로에서 1로 표시된 곳만을 통과하여, 좌측상단 -> 우측하단으로 가는 최단 경로의 수를 구하는 문제이다.
• 아래의 예시와 같이, n x m의 미로판이 주어지는데, 1과 0이 붙여서 주어지게 됨.

풀이

• 핵심 : BFS와 큐를 잘 이해하고 있는가.
• BFS는 상,하,좌,우를 탐색하여 다음 탐색할 그리드의 좌표를 큐에 쌓음.
• 큐는 first in first out 구조로써 먼저 큐에 쌓인 그리드의 좌표를 방문한다.
  목표까지 최단거리를 구하는 문제는 큐에 쌓인 좌표들을 하나씩 방문해가면 된다.
  목표에 가장 빨리 도달했을 때가 곧 최단거리가 됨.
• 아래 그림은 7x7미로판에서 1을 찾아 점차 경로를 찾는 과정을 보여준다.

... (중간 생략)

• 갈림길이 나왔을 시, 큐에 쌓인 순서대로 이동(양방향)하는 것을 볼 수 있음. 
• 이런식으로 이동시마다 현재까지 이동한 거리를 카운트
• 가장 먼저 목표 지점에 도달했을 때의 거리가 곧 최단거리가 된다.

 

코드

• 맵을 문자열로 받음, 벡터 형태로 줄마다의 문자열을 저장함. (# 입력을 벡터로 받을 시에는 push_back()을 이용해야 한다)
• 맵에서 이동한 경로를 체크해주는 2차원 벡터를 생성한다. 현재까지 이동한 거리를 저장
• 큐를 생성, 값을 쌍(pair)로 받음. (x,y) 좌표.
• dx, dy : 상,하,좌,우 이동할 방향에 대해서 선언

 

• 큐가 비어있을 때까지 수행
• First out의 좌표(x,y)에서부터 상,하,좌,우를 탐색하여 이동 가능한 좌표를 찾고 큐에 쌓는다.
• 예외처리, 맵의 범위를 벗어나거나, 이미 방문한 좌표, 이동할 수 없는 좌표는 제외.
• map_check[][]에 현재까지 이동한 거리를 계산해 저장한다.
• 목표 지점에 도달시 종료. (break가 빠졌음)

 

알게 된 점

• BFS는 큐를 기반인 것을 알고 있었지만, 막상 문제를 보니 스텍이 더 좋을 것 같아 시도했다가 성공하지 못하였음.
  스택으로 map에 대한 정보를 갈림길마다 저장하고, 목표지점까지 갔다가 다시 이전 갈림길로 백업하는 과정을 반복했는데, 필요없었던 작업이였다. 
  한 번 생각을 잘못하면 잘 못빠져 나오는 경향이 있음.
• 큐를 사용하면 더욱 효과적으로 처리할 수 있었지만, 큐에 대해서 재대로 활용하지 못했다.
• First in First out 순서대로 처리하면 간단히 해결할 수 있음.

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/9.%20BFS/%EB%AF%B8%EB%A1%9C%ED%83%90%EC%83%89%20(2178).cpp