백준 14940번 문제 바로가기

C++로 풀어보는 첫 bfs문제! python와 비교했을 때에 정의하는 방식만 다르지, 전체적인 구조는 동일해서 쉽게 익힐 수 있었다.

가장 헷갈렸던 부분은, deque을 정의하고 “좌표를 어떻게 전달할 것인가”는 문제였다. python같은 경우 tuple로 간단하게 전달하면 되지만, {x, y}로 전달하면 C++에서는 에러가 발생하기 때문이다. 다른 사람들의 bfs 구현 방식을 참고했는데, 대부분 pair 기능을 이용해서 좌표를 전달했다. make_pair(x, y)로 전달하면 마치 tuple 마냥 전달해줄 수 있다. 다시 그 값을 불러올 때에는 .front .second 처럼 점 연산자(.)를 통해 알아낼 수 있다.

bfs 알맞게 구현했는데 정답이 아니길래 봤더니 문제를 제대로 읽지 않은 잘못이었다.

원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

라고 제시되어있기 때문에 map값이 1이면서 visited값은 0인 점들의 경우 -1로 출력해주어야 한다.

#include <iostream>
#include <deque>
#define MAX 1000

using namespace std;

int N, M;
int map[MAX][MAX];
int visited[MAX][MAX];
int ans[MAX][MAX];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

deque<pair<int,int>> dq;

// bfs search
void bfs(int start_x, int start_y){
    visited[start_x][start_y] = 1;
    dq.push_back(make_pair(start_x,start_y));
    ans[start_x][start_y]=0;
    
    while (!dq.empty()){ // 갈 수 있는 모든 좌표 탐색
        int x = dq.front().first;
        int y = dq.front().second;
        
        dq.pop_front();
        for (int i=0; i<4; i++){ // 현제 좌표 기준 상하좌우 탐색
            int new_x = x + dx[i];
            int new_y = y + dy[i];
            if ((0<=new_x && new_x<N) && (0<=new_y && new_y<M)){
                if (!visited[new_x][new_y] && map[new_x][new_y]!=0){
                    visited[new_x][new_y] = 1;
                    dq.push_back(make_pair(new_x, new_y));
                    ans[new_x][new_y] = ans[x][y] + 1;
                }
            }
        }
    }
}

int main()
{
    cin >> N >> M;
    fill(&ans[0][0], &ans[N][M], 0);
    
    // map input
    int start_x, start_y;
    for (int i=0; i<N; i++){
        for (int j=0; j<M; j++){
            cin >> map[i][j];
            if (map[i][j] == 2){
                start_x=i, start_y=j;
            }
        }
    }
    
    // bfs search
    bfs(start_x, start_y);
    
    // result output
    for (int i=0; i<N; i++){
        for (int j=0; j<M; j++){
            if (map[i][j] == 1 && visited[i][j] == 0){
                ans[i][j] = -1;
            }
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}