[코드트리] BFS 탐색 / 네 방향 탈출 가능 여부 판별하기

네 방향 탈출 가능 여부 판별하기

n * m 크기의 이차원 영역의 좌측 상단에서 출발하여 우측 하단까지 뱀에게 물리지 않고 탈출하려고 합니다. 이동을 할 때에는 반드시 상하좌우에 인접한 칸으로만 이동할 수 있으며, 뱀이 있는 칸으로는 이동을 할 수 없습니다. 예를 들어 <그림 1>과 같이 뱀이 배치 되어 있는 경우 실선과 같은 경로로 탈출을 할 수 있습니다. 이 때 뱀에게 물리지 않고 탈출 가능한 경로가 있는지 여부를 판별하는 코드를 작성해보세요.

출처 codetree

입력 형식

첫번째 줄에는 n과 m이 공백을 사이에 두고 주어지고,

두번째 줄부터 (n+1)번째 줄까지는 각 행에 뱀이 없는 경우 1, 뱀이 있는 경우 0이 입력으로 공백을 사이에 두고 주어집니다. 시작 칸과 끝 칸에는 뱀이 주어지지 않는다고 가정해도 좋습니다.

• 2 ≤ n, m ≤ 100

출력 형식

좌측 상단에서 출발하여 우측 하단까지 뱀에게 물리지 않고 탈출 가능한 경로가 있으면 1, 없으면 0을 출력합니다.

---

나의 풀이

#include <iostream>
#include <queue>
using namespace std;
#define MAX_N 100
#define MAX_M 100

int n, m;
int a[MAX_N][MAX_M];

// bfs에 필요한 변수들 입니다.
queue<pair<int, int> > q;
bool visited[MAX_N][MAX_M];

bool InRange(int x, int y) { // 격자 안인지
    return 0 <= x && x < n && 0 <= y && y < m;
}

bool CanGo(int x, int y) { // 격자 안, 뱀이 없음, 방문한적 없음
    return InRange(x, y) && a[x][y] && !visited[x][y];
}

bool bfs(int x, int y){
    int dx[4] = {1,0,0,-1};
    int dy[4] = {0,1,-1,0}; // 격자이므로
    q.push(make_pair(x,y));
    visited[x][y]=1;

    while(!q.empty()){
        pair<int,int> a = q.front();
        q.pop();
        for(int i=0; i<4; ++i){
            int new_x = a.first + dx[i];
            int new_y = a.second + dy[i];
            if(CanGo(new_x, new_y)){
                visited[new_x][new_y] = 1;
                q.push(make_pair(new_x, new_y));
            }
        }
    }
    cout << visited[n-1][m-1];
}

int main() {
    cin>>n>>m;
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            cin>>a[i][j];
        }
    }
    bfs(0,0);
    return 0;
}

 

탐색 어렵다...

격자 문제이므로 상하좌우 4 방향으로 가는 것을 고려해야 하고, 

pair 만들어서 push해야함