[C++] 백준 2178번:미로 탐색

문제 링크

2178번: 미로 탐색

 

 

문제 설명

주어진 미로의 (1, 1)의 위치부터 (N, M)의 위치까지 이동할 때 지나야 하는 최소의 칸 수를 구해야 한다.

 

문제 풀이

시작 지점에서 도착 지점으로 지나야 하는 최소의 칸 수를 출력해야 하기 때문에 이 문제는 BFS로 해결할 수 있다. 보통 최소 거리는 모두 BFS로 해결하는 것 같다.

 

다른 칸으로 이동할 때는 서로 인접한 칸으로만 이동이 가능하다. 즉 상, 하, 좌, 우 로만 이동이 가능한 것이다. 아래 코드에서 보면 알겠지만 그것을 조금 더 쉽게 사용하기 위해 크기 4짜리의 dx[4], dy[4] 배열을 미리 선언해두었고 상, 하, 좌, 우로 이동하기 쉽게 값을 담아 두었다.

 

int dx, dy 배열은 다음과 같다.

int dx[4] = {-1, 1, 0, 0}

int dy[4] = {0, 0, -1, 1}

 

즉 현재 x좌표에 dx[0] 값을, 현재 y좌표에 dy[0] 값을 각각 더해주면 한 칸 위로 이동하는 효과를 가져올 수 있다. dx[1], dy[1]은 아래로, dx[2], dy[2]는 왼쪽으로, dx[3], dy[3]은 오른쪽으로 이동하는 효과를 가져올 수 있고, 미리 선언해둔 배열을 통해 코드를 조금 더 간결하게 작성할 수 있다.

 

 

코드

 

메모

bfs문제인데 dfs로 푸는 삽질을 했다.. PS를 원래도 못했지만 안 하다 보니 더 감이 떨어진건가.. 더 열심히 달려보자!

+valid라는 함수가 있어야 동작이 될 줄 알았는데 없어도 동작이 잘 된다. 이건 왜 그런 것인지는 아직 모르겠다.