[2178] 미로 탐색

• 입력: 세로N 가로M 미로지도(1: 갈 수 있는 곳 0: 갈 수 없는 곳)
• 출력: (1, 1)에서 (N, M)까지 가는 최소 칸 수
• 알고리즘: BFS
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> #include <queue> using namespace std; int main() { int n, m; scanf("%d%d", &n, &m); int maze[100][100]; bool visited[100][100]; for (int i = 0; i < n; i++) for(int j=0; j<m; j++) scanf("%1d", &maze[i][j]); int shell = 0; int here, x, y; queue<int> road; road.push(0); while (!road.empty()) { here = road.front(); x = road.front() / 100; y = road.front() % 100; road.pop(); if (x == n - 1 && y == m - 1) break; if (x < n - 1 && (maze[x + 1][y] == 1)) { maze[x + 1][y] = maze[x][y] + 1; road.push((x + 1) * 100 + y); } if (y < m - 1 && (maze[x][y + 1] == 1)) { maze[x][y + 1] = maze[x][y] + 1; road.push(x * 100 + y + 1); } if (x > 0 && (maze[x - 1][y] == 1)) { maze[x - 1][y] = maze[x][y] + 1; road.push((x - 1) * 100 + y); } if (y > 0 && (maze[x][y - 1] == 1)) { maze[x][y - 1] = maze[x][y] + 1; road.push(x * 100 + y - 1); } } printf("%d\n", maze[n - 1][m - 1]); return 0; }

미로 찾기 문제는 주로 BFS를 사용한다. 보통 BFS를 좀 달라서 많은 검색 후에 성공하였다. 

• 문제 참고: https://www.acmicpc.net/problem/2178