• 문제 : https://www.acmicpc.net/problem/2589

---

1. 문제 접근

최단거리 문제 - BFS로 풀기!!

• 해당 문제는 가로와 세로가 모두 50이하이므로, 충분히 모든 격자에 대해 완전탐색을 해도 시간복잡도가 나지 않음
• 모든 지점의 가중치(거리)가 동일하고 최단거리를 구하는 문제이기 때문에 BFS 사용 가능

---

2. 시행착오

• DFS로 풀다가 시간초과가 남

---

3. 코드 및 풀이

3.1 풀이

• visited 배열을 시작점으로부터 거리 구하는 배열로 사용함
• 땅(L)인 경우, 그리고 방문하지 않는 경우, bfs탐색
• 서로 간에 최단 거리로 이동하는데 있어(두 지점간 최단거리 탐색) 가장 긴 시간이 걸리는 지점을 찾아야 하므로(다른 connected component 후보군에서 bfs 결과값) 지속적으로 최댓값 갱신

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

const int max_l = 54;
const int dy[4] = {0, 1, 0, -1};
const int dx[4] = {1, 0, -1, 0};

int N, M, nx, ny;
int ret;
char adj[max_l][max_l];
int visited[max_l][max_l];

bool isValid(int y, int x){
    return (0 <= y && y < N && 0 <= x && x < M);
}

// 최단거리 + 가장 먼 보물 거리 갱신하는 BFS
void bfs(int y, int x){
    visited[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++){
            ny = y + dy[i];
            nx = x + dx[i];
            if(isValid(ny, nx) &&
            adj[ny][nx] == 'L' &&
            !visited[ny][nx])
            {
                q.push({ny, nx});
                // 여기서 visited는 0, 1 방문 유무가 아닌 최단거리 기록용
                visited[ny][nx] = visited[y][x] + 1;
                // 기존 보물 거리보다 크면 갱신
                ret = max(ret, visited[ny][nx]);
            }
        }
    }
}

int main(){
    
    // INPUT
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> adj[i][j];
        }
    }
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(adj[i][j] == 'L' && !visited[i][j]) {
                visited[i][j] = 1;
                bfs(i, j);
                memset(visited, 0, sizeof(visited));

            }
        }
    }
    // 출발을 1부터 시작하니, -1 해주기
    cout << ret - 1;
}

---

Reference