2178. 미로 탐색
백준 2178번 풀이
이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!
문제
풀이
아이디어
문제 자체는 이해하기 어렵지 않고 간단했다. 미로가 주어지고, (1, 1) 지점에서 (N, M) 지점까지 가기까지의 최단 경로를 구하는 문제이다.
미로의 모든 부분을 돌면서 가능한 모든 경우의 수를 찾아야 하기 때문에 완전탐색을 하면 될 것 같았고, 요새 계속 BFS로만 문제를 풀었던 것 같아서 이번엔 DFS로 풀어 보았다.
근데 시간초과가 났다.
왜 DFS로 풀었을 때에만 시간초과가 나는 것인지 이해가 안되어서 찾아봤는데 질문 게시판에 올라온 글을 보고 힌트를 얻었다. (참고 : 글 읽기 - dfs로 미로찾기 문제를 풀었는데;;)
DFS는 무조건 그래프를 모두 돌면서 모든 경우의 수를 비교해서 최단 길이를 찾아야 하는 반면에, BFS는 가장 처음 (N, M) 지점에 도달하는 시점의 경로의 길이가 최소 길이임이 보장되기 때문에 이 문제를 BFS로 접근한다면 모든 경우의 수를 찾을 필요는 없었다.
이런 차이가 벽이 많은 (이 문제에서는 맵에 0이 많은 경우)에서는 크게 느껴지지 않을 수도 있지만, 맵이 엄청 큰데, 벽이 거의 없어서 움직일 수 있는 경우의 수가 엄청 많을 경우에는 무시 못할 시간차이가 발생할 수 있을 것 같기도 했다.
그래서 BFS로 바꾸어서 문제를 풀었더니 무난하게 통과할 수 있었다.
… 사실 무난하진 않았고 런타임 에러 (OutOfBounds) 문제가 있긴 했었는데 바보같이 현재(그러니까 상하좌우로 이동하기 전)위치에서만 범위 검사를 하고, 상하좌우로 움직일 때 visited 배열을 접근하는 부분에서는 범위를 검사하지 않았던 것이다… 너무 초보적인 실수였는데 최댓값을 테스트케이스로 넣어보지 않아서 한참을 고민했었다. 바보… 이 문제를 푸는 다른 분들은 꼭 이동한 지점의 좌표의 범위를 잘 검사하시길 바랍니다…
코드
#include <iostream>
#include <tuple>
#include <queue>
#include <string>
#include <cstring>
#include <climits>
using namespace std;
int N, M;
int ans;
string map[100];
bool visited[100][100];
queue<tuple<int, int, int> > q;
int dir_y[4] = {-1, 0, 1, 0};
int dir_x[4] = {0, 1, 0, -1};
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
memset(visited, false, sizeof(visited));
for(int i = 0; i < N; i++)
cin >> map[i];
q.push(make_tuple(0, 0, 1));
int pos_y, pos_x, cnt;
while (!q.empty())
{
pos_y = get<0>(q.front());
pos_x = get<1>(q.front());
cnt = get<2>(q.front());
q.pop();
if (pos_y == N - 1 && pos_x == M - 1)
{
cout << cnt;
exit(0);
}
for(int i = 0; i < 4; i++)
{
int new_y = pos_y + dir_y[i];
int new_x = pos_x + dir_x[i];
if (new_y < 0 || new_y >= N || new_x < 0 || new_x >= M \
|| map[new_y][new_x] == '0' || visited[new_y][new_x])
continue;
visited[pos_y + dir_y[i]][pos_x + dir_x[i]] = true;
q.push(make_tuple(pos_y + dir_y[i], pos_x + dir_x[i], cnt + 1));
}
}
return (0);
}