[백준] 14940번 쉬운 최단거리 C++ 풀이

---

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• BFS

---

문제 설명

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

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

---

입력 설명

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

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

---

출력 설명

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

---

예제 입력

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 1 1

 

---

예제 출력

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 33 34

---

아이디어

목표지점은 단 한 개이므로 목표 지점을 먼저 찾고

거꾸로 생각해서 목표 지점에서 부터 모든 지점으로의 떨어진 거리를 구하는 것을 목적으로 한다.

---

알고리즘

입력을 저장할 벡터와 목표 지점으로부터 떨어진 거리를 저장한 벡터를 정의한다.

목표 지점을 찾는다.

목표 지점으로부터 시작되는 BFS를 돌면서 거리 저장 벡터에 거리를 저장하고 이를 visited로 사용한다.

BFS가 끝나면 이를 출력한다.

---

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
queue<pair<int,int>> q;
int xx,yy;
void search(int n, int m, vector<vector<int>> &vec, vector<vector<int>> &ans)
{
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++) 
                {
                    if(vec[i][j]==2)
                    {
                        xx=i;
                        yy=j;
                    }
                    else if(vec[i][j] == 0)
                        ans[i][j] = 0;
                }
        }
}
void BFS(vector<vector<int>> &vec, vector<vector<int>> &ans)
{
    q.push({xx,yy});
    ans[xx][yy] = 0;
    while(!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if(ans[x+1][y] == -1 && vec[x+1][y] == 1)
            {
                ans[x+1][y] = ans[x][y] + 1;
                q.push({x+1,y});
            }
          
            if(ans[x-1][y] == -1 && vec[x-1][y] == 1)
            {
                ans[x-1][y] = ans[x][y] + 1;
                q.push({x-1,y});
            }
           
            if(ans[x][y+1] == -1 && vec[x][y+1] == 1)
            {
                ans[x][y+1] = ans[x][y] + 1;
                q.push({x,y+1});
            }
            
            if(ans[x][y-1] == -1 && vec[x][y-1] == 1)
            {
                ans[x][y-1] = ans[x][y] + 1;
                q.push({x,y-1});
            }
        }
}
int main() 
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> vec(n+2,vector<int>(m+2,0));
    vector<vector<int>> ans(n+2,vector<int>(m+2,-1));
    for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++) cin>>vec[i][j];
        }
    search(n,m,vec,ans);
    BFS(vec,ans);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++) 
                    cout<<ans[i][j]<<" ";
            cout<<"\n";
        }
    return 0;
}

---

후기

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

모든 지점에서 목표 지점까지의 거리를 어떻게 구할지 생각하다가

거꾸로 목표 지점에서부터 모든 지점의 거리를 구하면 되겠다고 생각한 것이 이 문제의 결정적인 해결 방법이었던 것 같다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!