인프런 커뮤니티 질문&답변

3-B번 보물섬 문제를 풀다가. 각 육지마다 BFS를 하는 것보다, 한 컴포넌트에서 BFS_1로 임의의 한 점에서 가장 먼 점을 찾고, 찾은 가장 먼 점에서 BFS_2로 또 가장 먼 점을 찾으면, 해당 컴포넌트에서는 가장 먼 점의 길이를 구할 수 있다고 생각하고 풀이하였는데 틀린 이유를 잘 모르겠습니다...

이렇게 풀면 틀린 이유가 있을까요??

항상 수업 너무 잘 듣고 있습니다. 감사합니다!

#include <bits/stdc++.h>
using namespace std;

int n, m;
string a;
char mapp[54][54];
bool visited[54][54];
int dis[54][54];
int dy[] = {0,-1,0,1};
int dx[] = {1,0,-1,0};
queue<pair<int,int>> q;
queue<pair<int,int>> q2;
int max_val = 0;

pair<int,int> bfs_1(int y, int x){
  visited[y][x]=1;
  q.push({y,x});
  pair<int,int> here;
  while(q.size()){
    here = q.front();
    q.pop();
    for(int i=0;i<4;i++){
      int ny = here.first + dy[i];
      int nx = here.second + dx[i];
      if(ny<0||nx<0||ny>=n||nx>=m) continue;
      if(visited[ny][nx]) continue;
      if(mapp[ny][nx]=='W') continue;
      visited[ny][nx] = 1;
      q.push({ny,nx});
    }
  }
  return here;
}

int bfs_2(int y, int x){
  dis[y][x] = 1;
  q2.push({y,x});
  pair<int,int> here;
  while(q2.size()){
    here = q2.front();
    q2.pop();
    for(int i=0;i<4;i++){
      int ny = here.first + dy[i];
      int nx = here.second + dx[i];
      if(ny<0||nx<0||ny>=n||nx>=m) continue;
      if(dis[ny][nx]>0) continue;
      if(mapp[ny][nx]=='W') continue;
      dis[ny][nx] = dis[here.first][here.second] + 1;
      q2.push({ny,nx});
    }
  }
  return dis[here.first][here.second];
}


int main(){
  cin >> n >> m;
  for(int i=0;i<n;i++){
    cin >> a;
    for(int j=0;j<a.length();j++){
      mapp[i][j] = a[j];
    }
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(mapp[i][j]=='W') continue;
      if(visited[i][j]) continue;
      pair<int,int> ret_1 = bfs_1(i,j);
      int max_dis = bfs_2(ret_1.first, ret_1.second) -1;
      max_val=max(max_val,max_dis);
    }
  }
  cout << max_val;
  return 0;
}