[BOJ 2178번/C++] 미로 탐색

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

미로 탐색

문제

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

풀이

미로 찾기는 전형적인 DFS/BFS 문제이다.

이 문제는 DFS로 풀 수는 있겠지만, BFS로 푸는 것이 더 간단한 문제이다. (BFS는 항상 각 정점을 최단 경로로 방문한다.)

 

BFS로 한 노드를 방문할 때 마다 그 위치에 이동 횟수를 기록하면서 나아간다.

그렇게 해서 목적지에 도달하면, 그 지점에 기록되는 값이 최종 구하고자 하는 최단 거리가 된다.

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int N, M;
int maze[101][101];
int visited[101][101];
queue<pair<int, int>> q;

int main() {
    cin >> N >> M;
    
    for (int i = 1; i <= N; i++) {
        string tmp = "";
        cin >> tmp;
        for (int j = 1; j <= M; j++) {
            maze[i][j] = tmp[j - 1] - '0';
        }
    }
    
    q.push({ 1, 1 });
    visited[1][1] = true;
    
    while (!q.empty()) {
        pair<int, int> xy = q.front();
        int x = xy.first;
        int y = xy.second;
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx < 1 || nx > N || ny < 1 || ny > M)
                continue;
            if (!maze[nx][ny] || visited[nx][ny])
                continue;
            visited[nx][ny] = true;
            q.push({ nx, ny });
            maze[nx][ny] = maze[x][y] + 1;
        }
    }
    
    cout << maze[N][M] << endl;
    
    return 0;
 }