[C++/BOJ] 14940 : 쉬운 최단거리 (BFS) / test case

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

쉽다매....쉽다매..!!!!..!!

---

 

백준 실버 1.

예전에는 골5였던 듯 하다

 

하 진짜

혼자 끙끙대면서 한시간동안 열심히 풀었다

맞추고 나서 다시 코드를 보니 왜 이렇게 했지..?싶은 부분도 있었음 ㅋㅋㅋ

그래도 귀찮으니까 그냥 놔둔다.

 

심지어 처음에는 dp인줄 알았다가 풀면서 bfs인거 깨달았다.

 

제목은 함정이었다는 것도 깨달았다. (쉬운?)

 

 

1. 일단 입력용 이차원배열, visited 이차원배열, 결과 저장용 이차원배열,, 이렇게 3개가 필요하다

2. 시작점을 찾는다. 입력이 2인 부분을.. 입력받으면서 찾으면 되는데 나는 입력 다 받고 다시 반복문 돌리면서 했음ㅋㅋ

3. makeMap() 이게 bfs 함수이다. bfs는 별다른게 없는데 -1 출력하는게 은근 까다로웠음

4. 방문한 적이 없고 && 입력값이 1인 부분만 -1로 출력해야 한다.

 

 

-1이 나오는 테스트 케이스 하나 드리자면,

input

15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 0 1     -> 마지막 1이 0에 둘러싸여서 갇히게 됨

 

output

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25 
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26 
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0 
14 15 16 17 18 19 20 21 22 23 0 31 32 0 -1     -> -1로 출력.

 

 

나의 풀이

#include <iostream>
#include <queue>
using namespace std;

int n;
int m;
int in[1002][1002] = {0,};
int mat[1002][1002]={0,};
int visited[1002][1002] = {0,};

pair<int,int> searchTwo(){
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            if(in[i][j]==2) return {i,j}; // 이제 생각해보니 입력할때 이걸 잡아내도 되는데 왜이렇게 했지
        }
    }
    return {0,0};
}

bool canGo(int x, int y){
    if(visited[x][y]==1 || in[x][y]==0) return false;
    if(x<0 || y<0 || x>=n || y>=m) return false;
    return true;
}

void makeMap(){
    pair<int,int> idx = searchTwo();
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    queue<pair<int, int>> q;
    q.push(idx);
    mat[idx.first][idx.second] = 0;
    while(!q.empty()){
        pair<int, int> a = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i){
            int nx = a.first + dx[i];
            int ny = a.second + dy[i];
            if(idx == make_pair(nx,ny)){
                continue;
            }
            if(canGo(nx, ny)){
                q.push(make_pair(nx, ny));
                mat[nx][ny] = mat[a.first][a.second] + 1;
                visited[nx][ny] = 1;
            }
        }
    }

    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            if(visited[i][j]==0 && in[i][j]==1) mat[i][j] = -1; // 이거때메 한참 삽질함;;
            cout << mat[i][j] << " ";
        }
        cout << "\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n;++i){
        for (int j = 0; j < m; ++j){
            cin >> in[i][j];
        }
    }
    makeMap();
}