백준 2146:다리 만들기

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

이번문제는 보물섬입니다. 문제 풀때 가장 고민했던것은 '시작점을 어떻게 찾을 것인가'였는데요. 답은 가능한 모든 시작점에서 탐색을 하면서 가장 긴 거리를 찾는 것입니다! 나머지는 컴퓨터가 알아서 다해줄겁니다..

밑에는 제 코드입니다.

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<vector<char>> map;//지도
vector<vector<int>> visited;//방문체크
typedef pair<int, int> pos;//좌표
int r, c, tresure;
int dr[4] = { 0,-1,0,1 };
int dc[4] = { -1,0,1,0 };
 
bool isSafe(int row, int col) {
    if (row < 0 || r <= row || col < 0 || c <= col) return false;
    else return true;//범위 체크 함수
}
 
void bfs(void) {
    //**탐색할때 시작가능한 모든 지점에서 탐색해요**
    for (int row = 0; row < r; row++) {
        for (int col = 0; col < c; col++) {
            if (!visited[row][col]) {//방문하지 않았다면
                vector<vector<int>> check = visited;//맵의 방문체크 복사
                queue<pos> q;
                q.emplace(row, col);//시작 좌표
                check[q.front().first][q.front().second] = 1;//방문체크
                while (!q.empty()) {//큐가 빌때까지
                    pos cur = q.front();
                    for (int i = 0; i < 4; i++) {//4방 탐색
                        pos next = { cur.first + dr[i],cur.second + dc[i] };
                        if (isSafe(next.first, next.second) && !check[next.first][next.second]) {
                            //범위안에 있고 현재 섬에서 방문되지 않았다면
                            check[next.first][next.second] = check[cur.first][cur.second] + 1;
                            //거리 계산
                            q.push(next);//큐에 삽입
                        }
                    }
                    q.pop();
                }
 
                for (int i = 0; i < r; i++) {
                    for (int k = 0; k < c; k++) {
                        //탐색을 마친 후에 가장 먼 거리를 갱신
                        tresure = check[i][k] > tresure ? check[i][k] : tresure;
                    }
                }
 
            }
        }
    }
}
 
int main(void) {
    cin >> r >> c;
    map.resize(r);
    visited.resize(r);
    for (int i = 0; i < r; i++) {
        map[i].resize(c);
        visited[i].resize(c);
    }//r*c 지도를 만들어요
    for (int row = 0; row < r; row++) {
        for (int col = 0; col < c; col++) {
            cin >> map[row][col];
            if (map[row][col] == 'W') visited[row][col] = 1;
            //W면 그냥 방문했다고(방문하지 않기위해) 체크해요
        }
        cin.ignore();//문자 입력이므로 (enter)버퍼를 지워요
    }
    bfs();//탐색
    cout << tresure  - 1 << endl;
 
    return 0;
}