[백준(BOJ)/C++] 2178번: 미로 탐색 - 코딩밥상

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

2178번: 미로 탐색

 

• 접근 방법, 논리 흐름(알고리즘)

미로문제는 대표적인 bfs란것을 알고 있었기에 바로 문제 풀이에 들어갔는데, 처음부터 막힌 부분이 상하좌우의 결과에 따라 값이 결정된다는 것이었다. 이게 스터디때 배웠던 알고리즘이구나 생각했다.

미로를 2차원 평면 좌표로 생각하고 x,y값을 pair를 사용하여 관리했다.

bfs를 활용하기 위해 큐를 만들어 주고

다음과 같이 BFS를 사용하여 x,y값을 바꿔가며 가능한 지점으로 이동하면 되는것이다.

미로 밖의 좌표 또는 0인 미로칸은 이동 불가능하기 때문에 무시하고,

문제 조건에 맞는 1인 미로칸일 경우 이동해가며 큐에 해당 좌표를 넣고 그 전 값+1 이 해당 칸의 값이 될 것이다. 즉 해당 칸의 값은 그 칸으로 이동하기 위한 최솟값이 된다.

여기서 삽질을 잠깐 했었는데, 입력값이 붙어서 나오기 때문에 각 행마다 string으로 받고 형변환처리하여 정수배열에 저장해준다.

시작점을 (0,0)으로 돌려주면 답이 나온다.