[BOJ/백준] 14940 C++ 쉬운 최단거리

오늘의 문제는 14940 쉬운 최단거리 문제입니다!

현재 solved 기준 실버 1에 위치한 문제네요!

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

14940번: 쉬운 최단거리

 이 문제는 보자마자 느낌이 오시겠지만, 너비 우선 탐색$($BFS$)$ 문제입니다!

나쁘게 말하면 전형적이고 진부하지만, 좋게 말하면 BFS의 굉장히 정석적이고 처음 너비 우선 탐색에 대해 배우고 익히기 좋은 문제라고 생각합니다!

 

 일단 이 문제는 2차원 배열을 사용하는 BFS 문제입니다!

하나 약간 생각을 해야 하는 점이라면, 문제에 주어진 목표지점을 우리는 BFS의 시작지점이라고 생각하고 풀어야 한다는 것입니다!

 

자 문제를 본격 적으로 풀기 전에, 2차원 배열로 주어진 탐색 문제들은 어떻게 풀어야 보기 쉽고 간단하게 풀릴까요??

뭐,,, 사람마다 다르게 느끼겠지만, 아마도 pair 자료형을 써서 x좌표 y좌표로 치환해서 푸는 것이 문제를 다가가기 쉽다고 생각합니다

대부분,,, 그렇게,,, 하시는 것 같아요...! ㅋㅋㅋ

 

그리고, 2차원 배열로 주어지는 너비 우선 탐색 문제를 푸실 때에는 아래에 보여드리는 코드처럼 dx, dy를 배열로 미리 선언해 놓고, 현재 x, y에 있다고 할 때, for문으로 nx, ny를 탐색하는 것이 매우 정형화된 풀이이므로 이렇게 푸시는 것을 추천드립니다...!

저는 홍대병에 걸렸었을 때 다르게 풀어보려고 삽질을 하였으나,,, 정형화된 것에는 이유가 있는 법임을 깨달았답니다... ㅎ_ㅎ;;

 

아 그리고, 이 문제에서 가장 주의해야할 점이 있습니다. 

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 0
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은 -1로 바꿔주시고, 0은 0으로 출력해야 합니다! 

이걸 효율적으로 해결하기 위해선 방문처리를 위해 bool 배열을 쓰셨다면, 방문되지 않았는데 주어진 배열의 수가 1이라면 -1로 바꿔주시면 되겠습니다...!

 

아 그리고 이 문제를 조금은 더 직관적이고 확실하게 푸는 방법이 있는데요! BFS 풀다보면 자주자주 등장하는 상황이니 집중해 주세요!

아래에 있는 정답 코드에 BFS 함수 속 while문에 굳이 굳이

이런 식으로 for문을 만드는 이유는 여타 추가적인 변수 혹은 배열을 사용하지 않고, 문제에서 말하는 거리를 적어내기 굉장히 쉽기 때문에 이렇게 푸는 것입니다! 원리는 조금만 생각해 보시면 아실 수 있으실 거예요!

약간 설명드리자면,

$($0, 0$)$에서 출발하면, 큐에 $($1, 0$)$, $($0, 1$)$이 추가됩니다. -> 거리 1$($ cnt = 1 $)$

그럼 q_size는 2가 되겠죠? 그럼 $($1, 0$)$을 다음으로 탐색이 된다고 할 때, 큐에는 $($2, 0$)$, $($1, 1$)$이 추가되면서 큐에는 $($0, 1$)$, $($2, 0$)$, $($1, 1$)$이 담기게 됩니다.

하지만 저희가 미리 만들어 놓길 $($0, 1$)$까지만 for문에서 탐색하도록 만들었고 for문이 끝나면 cnt를 1 증가시키기 때문에, $($2, 0$)$과 $($1, 1$)$, $($0, 2$)$는 다음에 즉 cnt = 2일 때 돌게 되므로, 저 친구들은 거리가 2가 할당되게 됩니다!

이해... 되셨... 쬬? 제가 설명을 더럽게 본하는 것 같긴 한데,,, 암튼 원리는 이렇습니다!

 

 각설하고, 이러한 문제들은 여러 번 풀다 보면 "너무 뻔하다~ EZ~ 쉽다 쉬워~" 하는 생각이 금방 듭니다! 

백준에 문제도 차고 넘치니 날 잡고 여러 문제 풀어보세요! 코테에 자주 출제된다고들 하니 이런 건 미리미리 부셔놓길 추천드립니다!

아래에 정답 코드를 올려드리고 이만 물러나겠습니다! 

오타 및 오류 지적 혹은 궁금한 점은 댓글로 부탁드립니다!!

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

int N,M, cnt{0};
int Map[1001][1001];
int start_x, start_y;
bool visited[1001][1001];
queue<pair<int,int>> q;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

void BFS(int org_x, int org_y){
   q.push({org_x,org_y});
   visited[org_y][org_x]=true;
   Map[org_y][org_x]=cnt;
   cnt++;
   while(!q.empty()){
      int q_size = q.size();
      for(int i=0; i<q_size; i++){
         int x = q.front().first;
         int y = q.front().second;
         q.pop();

         for(int j=0; j<4; j++){
            int nx = x+dx[j];
            int ny = y+dy[j];
            if(nx<0||nx>=M||ny<0||ny>=N){
               continue;
            }
            if(visited[ny][nx]){
               continue;
            }
            if(!Map[ny][nx]){
               continue;
            }
            Map[ny][nx]=cnt;
            visited[ny][nx]=true;
            q.push({nx,ny});
         }
      }
      cnt++;
   }
}

int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin>>N>>M;
   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=j;
            start_y=i;
         }
      }
   }
   BFS(start_x,start_y);
   for(int i=0; i<N; i++){
      for(int j=0; j<M; j++){
         if(visited[i][j]){
            cout<<Map[i][j]<<' ';
         }
         else{
            if(!Map[i][j]){
               cout<<0<<' ';
            }
            else{
               cout<<-1<<' ';
            }
         }
      }
      cout<<'\n';
   }

   return 0;
}