[BaekJoon/백준] 2589번 보물섬

 

 

1167번(https://hevton.tistory.com/438) 처럼

트리의 지름 방식으로 문제를 풀어야 한다고 생각했다.

 

근데, 주어진 조건에서는 트리가 아닐 수도 있기 때문에... 예외가 있다고 한다.

여기 설명이 너무 잘 되어 있다.

 

그래서, 모든 경우를 다 해주는 방식을 사용했다.

그럼 O(N^3) 정도 나올텐데, N이 50이기 때문에 시간초과 걱정은 하지 않아도 된다.

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

int N, M;

char MAP[50][50];
bool VISIT[50][50];
int DEPTH[50][50];

int MAX_DEPTH;

int mx[4] = {0, 0, 1, -1};
int my[4] = {1, -1, 0, 0};

void bfs(int x, int y) {
    
    
    queue<pair<int, int>> que;
    que.push({x, y});
    VISIT[x][y] = true;
    
    
    while(!que.empty()) {
        
        int x = que.front().first;
        int y = que.front().second;
        
        que.pop();
        
        for(int i = 0; i < 4; i++) {
            
            int tx = x + mx[i];
            int ty = y + my[i];
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= M)
                continue;
            
            
            if(!VISIT[tx][ty] && MAP[tx][ty] == 'L') {
                que.push({tx, ty});
                
                DEPTH[tx][ty] = DEPTH[x][y] + 1;
                VISIT[tx][ty] = true;
                
                if(MAX_DEPTH < DEPTH[tx][ty])
                    MAX_DEPTH = DEPTH[tx][ty];
            }
        }
        
    }
    
    
    
}

int main() {
    
    
    cin >> N >> M;
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++)
            cin >> MAP[i][j];
    }
    
    
    
    for(int i = 0; i < N; i++) {
        
        for(int j = 0; j < M; j++) {
            
            if(!VISIT[i][j] && MAP[i][j] == 'L') {
                                
                bfs(i, j);
                
                memset(VISIT, 0, sizeof(VISIT));
                memset(DEPTH, 0, sizeof(DEPTH));
            }
        }
    }
    
    cout << MAX_DEPTH << "\n";
}

 

 

소요 시간 : 45분