문제 풀러 바로가기>
2589 :: 보물섬

💡주어진 것

입력 :
세로 크기(n) 가로 크기(m) assert(1 <= n,m <= 50);
육지(L)과 바다(W)로 표시된 보물 지도

• 문제 조건
  보물은 서로 간의 최단 거리로 이동하는 데 있어 가장 오랜 시간이 걸리는 육지 두 곳에 묻혀있다.

출력 :

보물이 묻혀있는 두 곳 사이를 최단거리로 이동하는 시간

💡 내가 생각한 로직

가중치(시간)이 같은 그래프에서 최단 거리 로직 = bfs를 이용하는 문제겠거니 싶었다.
여기서 2589번은 맵에서의 bfs를 어떻게 구현할 것인가? 를 묻는 문제였다.

void bfs(int y, int x) {
	queue<pair<int, int>> q;
    vis[y][x] = 1;
    q.push({y, x}); //방문 처리 후 큐에 밀어넣기
    while(q.size()) { //큐의 사이즈만큼 반복
    	tie(y, x) = q.front(); q.pop(); //밀어넣은 만큼 인접한 것을 반복
        for(int i = 0; i < 4; i++) {
        	int ny = y + dy[i]; int nx = x + dx[i];
            if(nx<0 || ny<0 || nx>=m || ny>=n) continue;
            if(a[ny][nx] == 'W' || vis[ny][nx]) continue;
            vis[ny][nx] = vis[y][x]+1;
            q.push({ny, nx}); //밀어넣기
       }
    }
}
        

💻[코드]

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
int n, m, mx, vis[54][54];
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
char a[54][54];
void bfs(int y, int x){
  memset(0, vis, sizeof(vis));
  vis[y][x] = 1;
  queue<pair<int, int>> q;
  q.push({y, x});
  while(q.size()) {
    tie(y, x) = q.front(); q.pop();
    for(int i = 0; i < 4; i++) {
      int ny = y + dy[i];
      int nx = x + dx[i];
      if(nx<0 || ny<0 || nx>=m || ny>=n) continue;
      if(vis[ny][nx] || a[ny][nx] == 'W') continue;
      vis[ny][nx] = vis[y][x] + 1;
      q.push({ny, nx});
      mx = max(mx, vis[ny][nx]);
    }
  }
}
int main() {
  ios_base::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 >> a[i][j];
    }
  }
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      if(a[i][j] == 'L') bfs(i, j);
    }
  }
  cout << mx - 1 << "\n";
}