[백준] JavaScript - 음식물 피하기 (1743)

개요

 

문제 이름: 음식물 피하기 (1743)
문제 링크: https://www.acmicpc.net/problem/1743
플랫폼: 백준
알고리즘 분류: DFS
소요 시간: 1시간

 

문제 전문

설명

입출력

 

문제 풀이

해설

이 문제는 DFS(깊이 우선 탐색) 알고리즘을 사용하여 음식물 쓰레기가 서로 인접한 경우 뭉쳐진 쓰레기의 최대 크기를 구하는 문제입니다.

 

문제를 요약하면 다음과 같습니다.

• N x M 크기의 통로가 주어집니다.
• 통로의 각 칸에는 음식물 쓰레기가 존재할 수 있습니다.
• 상하좌우로 인접한 쓰레기는 뭉쳐져서 더 큰 쓰레기가 됩니다.
• 가장 큰 음식물 쓰레기의 크기를 구해야 합니다.

문제 접근 방법은 다음과 같습니다.

1. 입력으로 N, M, K와 쓰레기의 좌표가 주어집니다. 이를 통해 통로를 나타내는 2차원 배열을 생성합니다.
2. 통로를 탐색하면서 음식물이 있는 칸을 발견하면 해당 위치에서 DFS를 시작합니다.
3. DFS로 인접한 음식물들을 모두 탐색하면서 쓰레기의 크기를 계산합니다.
4. 탐색이 끝나면 최대 크기와 비교하여 갱신합니다.
5. 모든 칸을 탐색한 후 최대 크기를 출력합니다.

즉, DFS 알고리즘을 적용하여 상하좌우로 연결된 음식물들의 크기를 구하고, 이를 전체 통로에 대해 반복하면서 가장 큰 값을 찾아내는 것이 핵심입니다.

 

시도

1차 시도  (성공)

// 파일 시스템을 불러오고 입력 데이터를 받아서 줄바꿈으로 분할
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 첫 번째 줄에서 세로(N), 가로(M), 음식물 개수(K)를 분리하여 숫자로 변환
const [N, M, K] = input[0].split(' ').map(Number);

// 음식물을 표시할 2차원 배열 생성 (1부터 시작하기 위해 N+1, M+1 크기로 생성)
const board = Array.from(Array(N + 1), () => Array(M + 1).fill(0));

// 방문 여부를 체크할 2차원 배열 생성
const visited = Array.from(Array(N + 1), () => Array(M + 1).fill(false));

// 입력받은 음식물의 좌표를 보드에 표시 (1로 표시)
for (let i = 1; i <= K; i++) {
    const [r, c] = input[i].split(' ').map(Number);
    board[r][c] = 1;  // 음식물이 있는 위치는 1로 표시
}

// 상하좌우 이동을 위한 방향 배열
// dx - 행(세로) 방향 이동
// dy - 열(가로) 방향 이동
const dx = [-1, 1, 0, 0];  // 상, 하, 좌, 우
const dy = [0, 0, -1, 1];  // 상, 하, 좌, 우

// DFS를 사용하여 연결된 음식물의 크기를 계산하는 함수
// x - 현재 행 위치
// y - 현재 열 위치
function dfs(x, y) {
    let size = 1;  // 현재 위치의 음식물 크기를 1로 시작
    visited[x][y] = true;  // 현재 위치 방문 처리

    // 상하좌우 네 방향을 순회
    for (let i = 0; i < 4; i++) {
        // 다음 위치 계산
        const nx = x + dx[i];
        const ny = y + dy[i];

        // 다음 위치가 보드 범위 내에 있는지 확인
        if (nx >= 1 && nx <= N && ny >= 1 && ny <= M) {
            // 다음 위치에 음식물이 있고(1) 아직 방문하지 않았다면
            if (board[nx][ny] === 1 && !visited[nx][ny]) {
                // 재귀적으로 연결된 음식물의 크기를 더함
                size += dfs(nx, ny);
            }
        }
    }
    return size;  // 총 음식물 크기 반환
}

// 가장 큰 음식물의 크기를 저장할 변수
let maxSize = 0;

// 보드의 모든 위치를 순회
for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= M; j++) {
        // 현재 위치에 음식물이 있고(1) 아직 방문하지 않았다면
        if (board[i][j] === 1 && !visited[i][j]) {
            // DFS로 현재 위치에서 연결된 음식물의 크기를 계산하고
            // 최대 크기와 비교하여 더 큰 값을 저장
            maxSize = Math.max(maxSize, dfs(i, j));
        }
    }
}

// 가장 큰 음식물의 크기 출력
console.log(maxSize);

위의 코드는 DFS를 사용하여 문제를 해결한 것입니다. 코드의 주요 내용을 설명하면 다음과 같습니다.

1. 파일 시스템 모듈 fs를 사용하여 표준 입력으로부터 데이터를 읽어옵니다. 입력 데이터는 줄바꿈으로 구분되어 있으므로 split('\n')으로 분할합니다.
2. 첫 번째 줄에서 세로(N), 가로(M), 음식물 개수(K)를 분리하여 map(Number)를 사용해 숫자로 변환합니다.
3. 음식물을 표시할 2차원 배열 board와 방문 여부를 체크할 2차원 배열 visited를 생성합니다. 이때 인덱스를 1부터 시작하기 위해 N+1, M+1 크기로 생성하고, 초기값을 0과 false로 설정합니다.
4. 입력받은 음식물의 좌표를 board 배열에 1로 표시합니다.
5. 상하좌우 이동을 위한 방향 배열 dx와 dy를 정의합니다.
6. DFS를 수행하는 함수 dfs(x, y)를 정의합니다. 이 함수는 현재 위치 (x, y)에서 시작하여 상하좌우로 연결된 음식물들의 크기를 계산하고 반환합니다.
   1. 현재 위치를 방문 처리하고, 크기를 1로 초기화합니다.
   2. 상하좌우 네 방향으로 이동하면서 다음 위치가 보드 범위 내에 있고, 음식물이 있으며 아직 방문하지 않은 경우 재귀적으로 dfs 함수를 호출하여 크기를 누적합니다.
7. 가장 큰 음식물의 크기를 저장할 변수 maxSize를 0으로 초기화합니다.
8. 보드의 모든 위치를 순회하면서 음식물이 있고 아직 방문하지 않은 위치에서 dfs 함수를 호출하여 연결된 음식물의 크기를 계산하고, maxSize와 비교하여 더 큰 값을 저장합니다.
9. 최종적으로 maxSize에는 가장 큰 음식물의 크기가 저장되어 있으므로 이를 출력합니다.

 

시간복잡도와 공간복잡도

• 시간복잡도: O(N * M)
  • DFS를 사용하여 보드의 모든 위치를 한 번씩 방문하므로 시간복잡도는 O(N * M)입니다.
• 공간복잡도: O(N * M)
  • 음식물을 표시할 2차원 배열 board와 방문 여부를 체크할 2차원 배열 visited의 크기가 O(N * M)이므로 공간복잡도는 O(N * M)입니다.

 

사용된 주요 메서드

• String.prototype.trim(): 문자열 양 끝의 공백을 제거하는 메서드입니다.
• String.prototype.split(separator[, limit]): 문자열을 지정한 구분자를 기준으로 분할하여 배열로 반환하는 메서드입니다. 구분자와 선택적으로 분할할 최대 개수를 인자로 받습니다.
• Array.from(arrayLike[, mapFn[, thisArg]]): 유사 배열 객체나 반복 가능한 객체로부터 새로운 배열을 생성하는 메서드입니다. 배열로 변환할 객체와 선택적으로 매핑 함수와 this로 사용할 값을 인자로 받습니다.
• Array.prototype.map(callback(currentValue[, index[, array]])[, thisArg]): 배열의 모든 요소에 대해 제공된 함수를 호출한 결과를 모아 새로운 배열을 반환합니다.
• Array.prototype.fill(value[, start[, end]]): 배열의 시작 인덱스부터 끝 인덱스까지 지정한 값으로 채우는 메서드입니다. 채울 값과 선택적으로 시작 인덱스와 끝 인덱스를 인자로 받습니다.
• Math.max(...args): 주어진 숫자 중 가장 큰 값을 반환하는 메서드입니다. 숫자들을 인자로 받습니다.