[백준/C++/BFS] 2178번 미로 탐색

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

2178번: 미로 탐색

문제

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

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

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

입력

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

출력

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

---

BFS 탐색 문제입니다. 위 미로 탐색과 같은 문제는 넓게 탐색하여 현재 위치한 자리에서 상,하,좌,우 중 선택해 방문하지 않고 숫자가 1이면 이전 위치에서의 숫자(cur_x,cur_y) 다음 위치에서의 숫자를 더해 갱신을 해줍니다.

이런 문제를 해결하기 위해선 배열에서 상,하,좌,우 좌표를 이동하는 배열을 사용해야 합니다.

int dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}}; //위 아래 오른 왼

현재 위치를 기준으로 상하좌우를 모두 건너가기 때문에 정해진 미로 밖을 벗어나는 경우가 발생할 수 있다. 이를 방지하기 위해 isInside 함수를 만들어 체크해 미로밖을 나가는 경우는 탐색하지 않도록 만들어준다.

bool isInside(int y, int x)
{
    return (y>=0&&y<n)&&(x>=0&&x<m);
}

bfs 함수를 실행하면서 queue<pair<int,int>> x,y좌표 모두 담을수있는 pair자료형 큐를 만들어주고 0,0좌표부터 시작해 n-1,m-1 좌표까지 탐색해줍니다. 마지막으로 n-1,m-1좌표 즉 문제에서 요구한 오른쪽 아래 끝좌표에 도달했을때 탐색이 완전히 종료되고 미로칸을 지나오면서 1을 더해주는 업데이트도 진행되었으니 return 값으로 마지막 칸을 해주면 끝나게 됩니다.

int bfs()
{
    int cur_x = 0, cur_y = 0;
    queue<pair<int,int>>q;
    q.push(make_pair(cur_y,cur_x));
    visited[cur_y][cur_x] = true;
 
    
    while(!q.empty())
    {
        cur_y = q.front().first;
        cur_x = q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int next_y = cur_y+dir[i][0];
            int next_x = cur_x+dir[i][1];
            if(isInside(next_y,next_x)&&visited[next_y][next_x]==false&&arr[next_y][next_x])
            {
                q.push(make_pair(next_y,next_x));
                visited[next_y][next_x] = true;
                arr[next_y][next_x] = arr[cur_y][cur_x]+1;
            }
        }
    }
    
    return arr[n-1][m-1];
    
}

전체소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstring>
#include <string>
using namespace std;

int n,m;

int arr[101][101] = {0,};
bool visited[101][101] = {false,};

int dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}}; //위 아래 오른 왼

bool isInside(int y, int x)
{
    return (y>=0&&y<n)&&(x>=0&&x<m);
}
int bfs()
{
    int cur_x = 0, cur_y = 0;
    queue<pair<int,int>>q;
    q.push(make_pair(cur_y,cur_x));
    visited[cur_y][cur_x] = true;
 
    
    while(!q.empty())
    {
        cur_y = q.front().first;
        cur_x = q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int next_y = cur_y+dir[i][0];
            int next_x = cur_x+dir[i][1];
            if(isInside(next_y,next_x)&&visited[next_y][next_x]==false&&arr[next_y][next_x])
            {
                q.push(make_pair(next_y,next_x));
                visited[next_y][next_x] = true;
                arr[next_y][next_x] = arr[cur_y][cur_x]+1;
            }
        }
    }
    
    return arr[n-1][m-1];
    
}




int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        string num;
        cin>>num;
        for(int j=0;j<m;j++)
        {
            arr[i][j] = num[j]-'0';
            //cout<<arr[i][j];
        }
        //cout<<endl;
    }
    cout<<bfs()<<endl;
    return 0;
}