[백준/c++] 2178번: 미로탐색

문제 링크 - https://www.acmicpc.net/problem/2178

🌱 문제

🌱 풀이

접근 방법

• 처음에 DFS로 풀려고 했지만 답이 계속 안나와서 BFS로 풀었다.
• 생각해보니 DFS는 연결된 경로의 모든것을 방문하는것이 목적이므로, 어떻게 이동할지는랜덤이기때문에?(알수없기 때문애) 최단경로를 찾을 수는 없다.
• BFS는 단계별로 진행되고, 경로를 전부 다 방문하기 때문에 최단경로 문제에서 사용 할 수 있다.

풀이

• arr은 미로배열을 입력받은 배열이고, answer은 시작점에서의 거리를 나타내는 배열이다.
• BFS를 돌면서 이전좌표의 answer값에 1씩 더해준다. 이때, 미로가1이고, 아직 방문하지 않은 좌표만 돌아야 하고, 배열 인덱스 범위체크도 해주어야 한다.
• (0,0)에서 bfs를 다 돌면 최종적으로 arr[n-1][m-1]에 시작점으로 부터의 경로가 담겨져 있다. 이것이 최단 경로가 된다.

🌱 코드

//2178번: 미로탐색

/*

2<=N,M,M=<=100

*/

#include <iostream>
#include <queue>
using namespace std;
int n,m;
char arr[100][100];
int answer[100][100];
bool visit[100][100];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

queue<pair<int,int>> q;

void bfs(int x,int y){  
    answer[x][y]=1;
    visit[x][y]=true;
    q.push(make_pair(x,y));

    while(!q.empty()){
        int cx=q.front().first;
        int cy=q.front().second;
        // cout<<"cx : "<<cx<<", cy: "<<cy<<"\n";
        q.pop();

        for(int i=0; i<4; i++){
            int nx=cx+dx[i];
            int ny=cy+dy[i];

            if(nx<0 || ny<0 || nx>=n || ny>=m)
                continue;
            
            if(arr[nx][ny]=='1' && visit[nx][ny]==false){
                answer[nx][ny]=answer[cx][cy]+1;
                q.push(make_pair(nx,ny));
                visit[nx][ny]=true;
            }
        }

    }

}


int main(){
    cin>>n>>m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>arr[i][j];
        }
    }
    bfs(0,0);
    cout<<answer[n-1][m-1]<<"\n";


}