백준 2178 - 미로탐색 C++

문제 설명

 

입력

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

출력

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

예제 입력 1 복사

4 6
101111
101010
101011
111011

예제 출력 1 복사

15

예제 입력 2 복사

4 6
110110
110110
111111
111101

예제 출력 2 복사

9

예제 입력 3 복사

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3 복사

38

예제 입력 4 복사

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4 복사

13

 

 

=> BFS를 이용해서 풀 수 있는 문제였습니다. 

=> 저는 시작점을 세지 않았기 때문에 맨마지막에 1을 더해서 출력하였습니다. 

=> 현재위치에서 갈 수 있는 위치에 대한 Validation과정에서 시간을 많이 소요하였습니다. 

=> nx는 N 미만이고 , ny는 M 미만입니다. 

=> 풀이과정은 아래에 이미지로 첨부하였습니다. 

 

문제풀이

 

 

#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int N,M; //초기변수값 N*M
string mp[100]; //주어진 미로를 저장할 map
int dis[100][100]; //최소거리를 저장할 변수, <0,0>에서 <0,1>을 가면 <0,1>에는 1이 저장된다.
int dx[4] = {0,1,0,-1};//인접한 곳만 갈 수 있도록 하는 변수
int dy[4] = {1,0,-1,0};
queue<pair<int, int>> quePair;

void BFS(int x, int y)
{
    quePair.push(make_pair(x,y));
    
    int tmpX, tmpY;
    while(!quePair.empty())
    {
        tmpX=quePair.front().first;
        tmpY=quePair.front().second;
        quePair.pop();
        
        for(int i=0; i<4; i++)
        {
            int nx = tmpX + dx[i];
            int ny = tmpY + dy[i];
            if( (nx >= 0) && (nx < N) && (ny >= 0) && (ny < M) && (mp[nx][ny] == '1') && (dis[nx][ny] == 0) ) //map은 string이니까 소괄호 해주고, dis는 int니까 필요없다.
            {
                quePair.push(make_pair(nx,ny));
                dis[nx][ny]=dis[tmpX][tmpY]+1;
            }
            
        }
        
    }
    
}

int main()
{
    
    cin >> N >> M;
    for(int i=0; i<N; i++)
    {
        cin >>mp[i];
    }
    BFS(0,0);
    
    cout <<dis[N-1][M-1]+1;
    return 0;
}