백준 2178번 : 미로 탐색

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

 

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

 

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 

이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

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

 

키워드 - BFS 기본 문제

접근법 - 큐와 맵을 이용하여 이동 경로를 적산 한다.

 

 

문제에 의하면 셀의 값이 1영역만 이동 할 수 있다.

초기 위치는 0,0 에서 시작 한다.

 

 

셀의 1인 영역을 이동한다고 가정하고 이동경로에 적산을 하면 각 칸마다 적산된 값을 확인 할 수 있다.

 

 

도착지점의 배열의 값은 14 이다.

문제에서 제약 사항인 

"칸을 셀 때에는 시작 위치와 도착 위치도 포함한다."

유의 해야 한다.

 

 

Source

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <map>
using namespace std;

// 상 하 좌 우 
int dy[] = { 0, -1, 1, 0};
int dx[] = { -1, 0, 0, 1};

// 보드 초기화 
vector<string> board;

// 보드 크기 
int n, m;

int main() {

    std::ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    board = vector<string>(n);
    for (int i = 0; i < n; ++i) cin >> board[i];
    
    queue<pair<int, int>> qu;
    map<pair<int, int>, int> myMap;
    pair<int, int> src;
    
    // 처음 위치 
    src.first = 0;  // y
    src.second = 0;    // x
    
    qu.push(src);
    myMap[src] = 1;

    while (qu.empty() == false) {
        pair<int, int> here = qu.front(); qu.pop();
        int cost = myMap[here];
        for (int dir = 0; dir < 4; ++dir) {
            int ny = dy[dir] + here.first;
            int nx = dx[dir] + here.second;

            // board 영역을 넘어 갈땐 연산하지 않음
            if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
            
            // board 의 값이 1 경우만 움직일 수 있음
            if (board[ny][nx] != '1') continue;

            pair<int, int> there;
            there.first = ny; there.second = nx;

            // 순회 하지 않은 경로만 탐색 한다.
            if (myMap.count(there) == 0) {
                qu.push(there);

                // 현재 까지 이동한 경로를 카운트 한다.
                myMap[there] = cost + 1;
            }
        }
    }

    // 도착 지점
    pair<int, int> snk;
    snk.first = n - 1; snk.second = m - 1;

    // 도착 지점에 도착 했을 때 총 거리를 출력 한다.
    cout << myMap[snk] << endl;
    return 0;
}