[JavaScript] 백준 2589 보물섬 (JS)

보물섬

📚 문제 설명

N개의 행과 M개의 열로 이루어진 지도가 있다.
여기서 "L" 은 육지를, "W"는 바다를 의미할 때,
보물은 육지에서 서로 가장 멀리 떨어져 있는 2개의 위치에 존재한다고 한다.
이 문제는 두 보물의 최단 거리를 구하는 문제이다.

위의 그림을 예시로 들면 2개의 색칠된 부분에 보물이 있고 해당 보물의 거리는 8이다.

👨🏻‍💻 풀이 과정

최단 거리를 구하는 문제이기 때문에 자연스럽게 BFS(너비 우선 탐색)을 생각하게 되었고,
MAP 을 N * M 의 지도라고 했을 때, MAP 의 각각의 "L" 에서 다른 "L"까지의 최장 거리Distance를 구하고
Distance 값이 가장 큰 값이 바로 보물의 두 위치인 것이다.

로직을 간략히 설명하면 다음과 같다.

• MAP을 돌며 만약 "L" 이면 BFS(x,y)를 실행.
• BFS(x,y) 를 실행하여 Distance를 찾아서 리턴.
• 리턴 받은 값의 최댓값을 찾아서 출력.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

    let [N, M] = input.shift().split(' ').map(Number);
    const MAP = input.map(v => v.split(''));
    let dx = [1, -1, 0, 0];
    let dy = [0, 0, 1, -1];
	//너비 우선 탐색
    const BFS = (X, Y) => {
      	// 거리를 담을 배열
        let CountMap = new Array(N);
      	// 최장 거리를 넣어줄 변수
        let Distance = 0;
      	// 배열 초기화
        for (let i = 0; i < N; i++) {
            CountMap[i] = new Array(M).fill(0);
        }
      	// BFS를 위한 큐 생성
        let Queue = [[X, Y]];
      	// 초기 값 
        CountMap[X][Y] = 1;
      	// shift() 를 안쓰기 위해 인덱스 값으로 이용
        let idx = 0;
        while (Queue.length > idx) {
            const [x, y] = Queue[idx];
          	// 상하좌우 움직임
            for (let i = 0; i < dx.length; i++) {
                const NextX = x + dx[i];
                const NextY = y + dy[i];
              	// 만약 지도를 벗어나면 실행 X
                if (NextX >= 0 && NextX < N && NextY >= 0 && NextY < M) {
                  	// 다음 위치가 육지이고, 아직 가지 않은 곳이라면 갱신.
                    if (MAP[NextX][NextY] === 'L' && CountMap[NextX][NextY] === 0) {
                        CountMap[NextX][NextY] = CountMap[x][y] + 1;
                        Queue.push([NextX, NextY]);
                      	// 최장거리 변경
                        if (Distance < CountMap[NextX][NextY]) Distance = CountMap[NextX][NextY];
                    }
                }
            }
            idx++
        }
      	// 1에서부터 거리를 쟀기 때문에 -1 을 해줘야함
        return Distance - 1;
    };
	// 전체 맵을 돌며 L인 부분에서만 BFS를 이용해 거리를 찾아줌
    const solution = () => {
        let max = 0;
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < M; j++) {
                if (MAP[i][j] === 'L') {
                    let tmp = BFS(i, j);
                  	// 거리 값이 최대인 것을 찾기 위해
                    if (max < tmp) max = tmp;
                }
            }
        }
        console.log(max);
    };
    solution();

🧐 후기

오랜만에 BFS를 사용하는 문제를 푸니 처음 BFS/DFS를 접했을 때가 생각이 났다.
처음 BFS/DFS를 접했을 때는 도저히 이해가 안 됐는데, 이제는 조금씩 알 것 같다는 느낌이 들고, 그래도 그때보다는 조금 실력이 늘지 않았나 하는 생각을 하게 되었다.