문제 바로가기
접근방법
- 미로는 대표적인 DFS/BFS 문제이다.
- 2인 지점에서 시작을 한다.
- 0인 곳만 밟고 다닌다.
- 3을 만나면 종료
풀이
#include <cstdio>
#include <iostream>
#include <queue>
#define MAX 16
using namespace std;
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, -1, 0, 1 };
int maze[MAX][MAX];
int bfs(int y, int x) {
queue<pair<int, int>> q;
q.push(make_pair(y, x));
while (!q.empty()) {
y = q.front().first;
x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (maze[ny][nx] == 3)
return 1;
if (ny >= 0 && ny < MAX && nx >= 0 && nx < MAX) {
if (maze[ny][nx] == 0) {
q.push(make_pair(ny, nx));
maze[ny][x] = 1;
}
}
}
}
return 0;
}
int main() {
int test_case, start_y, start_x, tc;
for (test_case = 1; test_case <= 10; test_case++) {
cin >> tc;
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
scanf("%1d", &maze[i][j]);
if (maze[i][j] == 2) {
start_y = i;
start_x = j;
}
}
}
cout << "#" << tc << " " << bfs(start_y, start_x) << "\n";
}
}