[백준] 2589번: 보물섬

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

2589번: 보물섬

문제 이해

최단 거리를 구하는 문제이므로 BFS를 사용하면 된다. 

모든 땅 중 두 개를 골라 그 사이의 최단거리를 구해야 하고, 그렇게 나온 최단거리들 중에 최장 거리를 고르는 것이 답이다.

그러므로 모든 땅들 중 두 개씩 짝지어서 모두 BFS를 해야한다.

 

시간 복잡도를 살펴보면, 가로 세로 최고 50개이니까, 50*49번의 BFS가 일어나고, 각 BFS별로 약 50*50번의 루프가 발생한다치면 2500*2500 = 6250000이므로 모든 경우를 탐색해도 제한시간을 넘기지 않을 것이다. 

 

작성 코드

C

#include <stdio.h>

int Y, X;
char map[50 + 5][50 + 5];
int max;

// 방향벡터
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };

// 큐
typedef struct POS {
    int y;
    int x;
    int d; //거리
}POS;

POS q[50 * 50 + 10];
int wp, rp;

void enq(int y, int x, int d) {
    q[wp].y = y;
    q[wp].x = x;
    q[wp].d = d;
    wp++;
}

POS deq(void) {
    POS tmp = q[rp];
    rp++;
    return tmp;
}

int empty(void) {
    return wp == rp;
}

POS qback(void) {
    return q[wp - 1];
}

void BFS(int sy, int sx, int sd) {
    
    // 초기화
    int visited[50 + 5][50 + 5] = { 0, };
    rp = 0, wp = 0;

    enq(sy, sx, sd);
    visited[sy][sx] = 1;

    while (!empty()) {

        POS cur = deq();
        for (int i = 0; i < 4; i++) {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];

            if (nx < 0 || nx >= X) continue;
            if (ny < 0 || ny >= Y) continue;
            if (visited[ny][nx] != 0) continue;
            if (map[ny][nx] == 'W') continue;

            enq(ny, nx, cur.d + 1);
            visited[ny][nx] = cur.d+1;
        }
    }

    // 큐 맨 뒤에는 마지막으로 방문한 노드가 담겨있다
    if (q[wp - 1].d > max) max = q[wp - 1].d;

}

int main(void) {

    // 입력 받기
    scanf("%d %d", &Y, &X);
    for (int i = 0; i < Y; i++) {
        scanf("%s", &map[i]);
    }

    // 모든 땅에 대해 BFS를 진행한다. 
    for (int i = 0; i < Y; i++) {
        for (int j = 0; j < X; j++) {
            if (map[i][j] == 'L') BFS(i, j, 0);
        }
    }

    printf("%d", max);

    return  0;
}

visited 배열과 큐를 초기화 해줘야 한다는 점을 잊으면 안된다!

 

C++

#include <iostream>
#include <queue>

using namespace std;

int Y, X;
char map[50+5][50+5];
int ans = 0;

// 방향벡터
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};

// 큐
typedef struct POS{
    int y;
    int x;
    int d;
}POS;

queue<POS> q;

void BFS(int sy, int sx, int sd){

    // 초기화
    int visited[50+5][50+5] = {0,};
    POS tmp = {sy, sx, sd};
    q.push(tmp);
    visited[sy][sx] = 1;
    
    while(!q.empty()){

        POS cur = q.front();
        q.pop();
        for(int i = 0; i<4; i++){
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];

            if(nx < 0 || nx >= X) continue;
            if(ny < 0 || ny >= Y) continue;
            if(visited[ny][nx] == 1) continue;
            if(map[ny][nx] == 'W') continue;

            POS tmp = {ny, nx, (cur.d+1)};
            q.push(tmp);
            visited[ny][nx] = 1;
        }
    }
    // 큐 맨 뒤에는 마지막으로 방문한 노드가 담겨있다
    if(q.back().d > ans) ans = q.back().d;
}

int main(void){

    // 입력 받기
    scanf("%d %d", &Y, &X);
    for(int i = 0; i<Y; i++){
        scanf("%s", &map[i]);
    }

    // 모든 땅에 대해 BFS를 진행한다. 
    for(int i = 0; i<Y; i++){
        for(int j = 0; j<X; j++){
            if(map[i][j] == 'L') BFS(i, j, 0);
        }
    }

    printf("%d", ans);

    return  0;
}

C++을 사용하면 시간이 확실히 더 오래걸린다. (아래가 C, 위가 C++)