2178. 미로 탐색
문제링크 : https://www.acmicpc.net/problem/2178
# 문제 설명
기본적인 BFS 문제였다.
문제에서 구하는 것은 (1,1) 칸에서 출발해서 (N, M)의 위치로 이동할 때 지나야 하는 '최소의 칸 수'를 구하는 것이기 때문에 대표적인 최단거리 문제라고 보면 된다. 즉, BFS를 사용하면 편리한 문제다.
- 여기에서 주의해야할 점을 정리하면 다음과 같다.
1) '1'이 이동할 수 있는 칸이고 '0'이 이동할 수 없는 칸이다.
2) 칸을 셀 때는 시작 위치와 도착 위치도 포함한다.
3) 미로가 주어질 때 숫자가 '붙어 있는' 한 줄씩 주어진다.
2)를 위해서 BFS를 (1,1)부터 시작할 때 거리값을 0이 아닌 1부터 주고 시작했다. (시작 위치를 포함하기 위함임)
3) 구현을 위해서 우선 string input을 선언해서 한 줄로 받은 다음에 map[i][j] = input[j-1] - '0'의 형태로 숫자로 변환해서 받았다.
# 문제 풀이
int map[101][101]을 선언해서 입력값의 미로를 저장하고, Queue에 (1,1)부터 시작하되 dis[101][101] ( (1,1)에서 각 지점까지 도달하는 최단 거리를 저장할 이차원 배열)에서 dis[1][1]의 값을 1로 지정하고 시작했다.
또, int min_dis는 최종적으로 (1,1)에서 (N,M)까지 도달하는 데에 최단 거리를 저장할 것이기 때문에 용이한 비교를 위해 초기값을 INT_MAX로 선언하였다. (#include 필수!)
그리고 큐에서 돌다가 만일 큐의 top.x, top.y 좌표가 (N,M)에 도착하면 min_dis값과 dis[N][M] 값을 비교해서 더 작은 쪽으로 min_dis에 업데이트하기로 했다. ( (N,M)에 서로 다른 경로로 여러 번 도착할 수 있는 경우의 수도 있을 것이므로)
또, 현재 좌표(top.x, top.y)의 인접한 상하좌우를 살펴서 접근할 수 있는 곳인지(map[xx][yy] == 1), 방문하지 않았거나(dis[xx][yy] == 0), 이미 도달했더라도 더 최단거리로 도달한 것인지(dis[xx][yy] > dis[top.x][top.y] + 1이 참이면 지금 경로가 이전보다 더 최단거리)를 판단해서 이에 해당할 경우에만 큐에 좌표를 넣는다.
마지막으로 min_dis 최종 업데이트 값을 출력한다.
// 2178. 미로 탐색
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;
struct point {
int x;
int y;
};
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int map[101][101];
int dis[101][101];
int N, M;
int min_dis = INT_MAX;
int main() {
// 1: 이동할 수 있는 칸, 0: 이동할 수 없는 칸
// (1,1) -> (N,M) 위치로 이동할 때 최소의 칸 수.
cin >> N >> M;
for (int i = 1; i <= N; i++) {
string input;
cin >> input;
for (int j = 1; j <= input.size(); j++) {
map[i][j] = input[j-1] - '0';
}
}
queue<point> Q;
Q.push({ 1,1 });
dis[1][1] = 1;
while (!Q.empty()) {
point top = Q.front();
Q.pop();
if (top.x == N && top.y == M) {
if (min_dis > dis[N][M]) min_dis = dis[N][M];
continue;
}
for (int i = 0; i < 4; i++) {
int xx = top.x + dx[i];
int yy = top.y + dy[i];
if (xx < 1 || yy < 1 || xx > N || yy > M) continue;
if (map[xx][yy] == 0) continue;
if (dis[xx][yy] == 0) {
dis[xx][yy] = dis[top.x][top.y] + 1;
Q.push({ xx, yy });
}
else if (dis[xx][yy] > dis[top.x][top.y] + 1) {
dis[xx][yy] = dis[top.x][top.y] + 1;
Q.push({ xx, yy });
}
}
}
cout << min_dis << endl;
}# 개선점 및 참고할 점
지금 생각해보니, dis[101][101] 이차원 배열에 (1,1)부터 시작해서 각 좌표에 도달할 때의 최단 거리를 계속 업데이트하는 구조라면 int min_dis를 선언하지 않고 dis[N][M]을 그대로 답으로 출력했어도 같은 답이 나왔을 것으로 생각된다. 더욱 코드를 간결히 구성하려면 이 점을 개선했으면 좋겠다.
