2178. 미로탐색

이번에 풀어볼 문제는 백준의 2178 미로탐색이다.

2178번: 미로 탐색

DFS를 이용하여 문제를 풀었다. 

 

 

< Code 설명 >

#include <iostream>
#include <queue>

using namespace std;

#define MAX 100

int dx[4]={-1,1,0,0};	// X 좌표 이동범위
int dy[4]={0,0,-1,1};	// Y 좌표 이동범위
                        // -> 상하좌우
                        
int arr[MAX][MAX];      // 미로
int n, m;

void bfs(int v, int w){
    queue<pair<int,int>>q;
    q.push(make_pair(0,0));
    while(!q.empty()){
        v=q.front().first;  // x좌표
        w=q.front().second; // y좌표
        q.pop();	    // 필요한 x,y좌표 저장했으니 queue에서 꺼냄
        for(int i=0; i<4; i++){ // 4방향을 탐색함(즉, 길(1)을 찾는 것)
            int nx = v+dx[i];   
            int ny = w+dy[i];
            if(nx < 0 || ny < 0 || nx > n-1 || ny > m-1) //탐색 범위 벗어날경우
                continue;
            if(arr[nx][ny]==1){	// 길이 있을 경우
                q.push(make_pair(nx,ny)); // queue에 넣어줌
                arr[nx][ny]=arr[v][w]+1;  // 이동했기 때문에 +1
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%1d",&arr[i][j]);
        }
    }
    bfs(0,0);
    cout << arr[n-1][m-1] << endl;        // 우리가 구하는 n,m좌표의 결과 출력
    return 0;
}

반드시 알아야할 TIP!!

-> 최단거리에 대한 문제를 어떻게 접근할지 고민하기

-> 좌표탐색을 생각해야함 즉, 상하좌우탐색 -> 대각선 탐색 문제도 존재할 것으로 예상