#2178 미로 탐색 (C++)

링크 : www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

조건이 각각의 숫자들이 '붙어서' 입력받는 관계로, 먼저 문자형으로 값을 입력 받고 int형으로 바꾸는 과정이 필요되었다.

아스키 코드를 활용한 형변환을 활용했는데, 자세한 사항은 2667번 단지번호붙이기의 초입부를 참고해보자.

 

문제풀이는 다음과 같다.

(1) 값을 입력받을 때, 문자열로 입력받고 해당 값의 -48, 즉, int형으로 변환하여 배열에 저장한다.

(2) 맨 처음과 맨 끝도 이동 범위에 포함이 되므로, ch배열의 [1][1]에는 1을 저장한다.

*ch배열 : 누적된 움직임의 값을 저장해주며, 동시에 해당 배열을 방문한 경험이 있는지를 체크해준다. 

(3) 1,1부터 bfs를 진행한다. 큐에 값을 저장할때는 배열의 y축과 x축을 같이 저장해야하므로 pair를 이용해 저장해준다. 

(4) 상 / 하 / 좌 / 우로 for문을 돌리며, 해당 위치가 값의 범위를 넘지 않고 (1이상 m, 혹은 n 이하) 배열 원본의 값이 0이 아니며 (1의 값만 이동이 가능), 방문한 경험이 없다면 (방문 경험이 없으면 ch배열의 값은 0이어야한다) 해당 위치의 ch배열에 기존 값에 +1을 계산하여 누적된 움직인 값을 저장해준다. 

(5) 이때 해당 위치가 n,m일 경우, 기존의 값에 + 1을 하여 출력한 뒤 코드를 종료해준다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n = 0, m = 0, ty = 0, tx = 0, ny = 0, nx = 0;
int arr[101][101], my[4] = {1,0,-1,0}, mx[4] = {0,1,0,-1};
int ch[101][101];

bool track(int y, int x){
    if(y<1||y>n||x<1||x>m||arr[y][x]==0||ch[y][x]>0) return false;
    return true;
}

void bfs(int y, int x){
    queue<pair<int,int>> q;
    q.push(make_pair(y,x));
    while(!q.empty()){
        ty = q.front().first;
        tx = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            ny = ty + my[i];    
            nx = tx + mx[i];
            if(ny==n&&nx==m){
                cout << ch[ty][tx] + 1 << "\n";
                exit(0);
            }
            if(track(ny,nx)){
                q.push(make_pair(ny,nx));
                ch[ny][nx] = ch[ty][tx] + 1;
            }
        }
    }
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    char c;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> c;
            arr[i][j] = c-48;
        }
    }

    ch[1][1] = 1;
    bfs(1,1);

    return 0;
}