[BOJ/백준] 21736 C++ 헌내기는 친구가 필요해

오늘의 문제는 백준 21736 "헌내기는 친구가 필요해"입니다!

굉장히 공감이 가는 내용을 가지고 있는 문제입니다...ㅎㅡㅎ...;

이 문제는 solved 기준 실버 2에 위치한 문제로 BFS나 DFS로 푸는 문제들 중에선 쉬운 문제에 속합니다!!

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

21736번: 헌내기는 친구가 필요해

사실 이 문제가 BFS와 DFS로 풀리는 문제를 많이 접해보시지 않으신 분이라면,

왜 이게 쉬운 문제에 속하는 지 이해가 안 가실 수 있습니다만,

사실 이 문제는 너무나 Well-Known 형식의 정형화된 문제입니다.

매우 정석적이고, 특정 부분에서의 변주 없이 대부분의 사람들이 탐색 문제를 푸는 행동 순서에 맞춰 푼다면

너무나 편하게 풀리는 문제입니다...!

물론 이 "대부분의 사람들이 탐색 문제를 푸는 행동 순서"가 무엇인지

처음 접하실 때는 매우 멀게 느껴지실 수 있습니다...

제가 막 백준 실버 쯤 달고 처음 BFS, DFS를 접했을 때 그랬으니까요... ㅋㅡㅋ

이러한 정형화된 행동 순서에 대해서는 따로 포스팅을 올릴 예정이니

나중에 이 게시물에도 링크를 걸겠습니다!

 

이제 문제에 대해 이야기를 해보면!

char 자료형을 갖는 2차원 배열이 주어지고, 도연이의 위치가 알파벳 I로

한 번만$($도연이는 나루토가 아니니까...!$)$ 주어지게 됩니다.

그리고 X에 사방이 막히지 않아서 접근 가능한 P를 찾아 헤메는 느낌인 문제네요!

 

그러면, 이 문제를 볼 때 제 의식의 흐름을 말씀 드려보자면!

"아 2차원 배열로 문제가 주어지네 일단 2차원 배열 선언하고 입력받자

그리고 읽어보니 dx, dy를 설정해서 {x, y}에 대해 {nx, ny}를 만들면 되겠고,,,

BFS로 풀 생각이니 위치를 저장하는 queue를 하나 만들자

그리고 I가 나타났을 때를 if문으로 받아서 위치를 특정 변수에 저장해 놓고

이걸 BFS의 시작 지점으로 정하면 되겠네

또,,, 예외 처리는 확실히 하고,

이미 갔던 곳을 또 가게 돼서 삥글삥글 돌 수도 있으니까

visited라는 2차원 bool 자료형 배열을 만들어서

방문 처리를 확실히 하면 문제없이 풀리겠네"

정도로 생각했습니다...!

 

물론 이게 처음 한 번에 쫙~~~ 생각 나기 보다는

상황에 맞춰 풀다보면 자연스레 따라오는 느낌이랄까요...?

그리고, 이 문제에서 보이는 것 처럼

상, 하, 좌, 우로 움직이기 때문에 dx, dy를 선언하는 느낌의 포맷은

BFS를 푸는 굉장히 노골적인 방식이니까 익숙치 않으시다면,

아래에 정답 코드를 보시고 눈에 많이 익혀 놓으시길 추천드립니다!

 

자 이제 정답 코드를 보여드리고 전 이만 물러나겠습니다~_~

혹시 오타나 문제점 있으시면 댓글로 부탁드립니다!

 

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

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

void BFS(int X, int Y){
   q.push({X,Y});
   visited[Y][X]=true;
   while(!q.empty()){
      int x = q.front().first;
      int y = q.front().second;
      q.pop();

      for(int i=0; i<4; i++){
         int nx = x+dx[i];
         int ny = y+dy[i];
         if(visited[ny][nx]){
            continue;
         }
         if(nx<0||nx>=M||ny<0||ny>=N){
            continue;
         }
         visited[ny][nx]=true;
         if(Map[ny][nx]=='O'){
            q.push({nx,ny});
         }
         else if(Map[ny][nx]=='P'){
            ans++;
            q.push({nx,ny});
         }
      }
   }
}

void Solve(){
   BFS(start_x,start_y);
   if(!ans){
      cout<<"TT"<<'\n';
   }
   else{
      cout<<ans<<'\n';
   }
}

void Init(){
   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]=='I'){
            start_x=j;
            start_y=i;
         }
      }
   }
}

int main(){
   cin.tie(nullptr)->ios_base::sync_with_stdio(false);
   Init();
   Solve();
   return 0;
}