백준 2842 집배원 한상덕 코드 리뷰 (node.js)

DFS 알고리즘에 대해서 내가 약한 거 같다.. 패스트캠퍼스 강의를 들으면서 먼저 풀었는데, 실패해서 강의자분의 코드를 리뷰하면서 dfs 알고리즘에 대해서 정리하고자 게시글을 쓰게 되었습니다.

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

2842번: 집배원 한상덕

const fs = require('fs');
const input = fs
  .readFileSync(__dirname + '/input.txt')
  .toString()
  .split('\n');

const n = +input[0];
const arr = [];
for (let i = 1; i <= n; i++) {
  arr.push(input[i].split(''));
}

const height = [];
for (let i = n + 1; i <= n + n; i++) {
  height.push(input[i].split(' ').map(Number));
}

let dx = [-1, -1, -1, 0, 0, 1, 1, 1];
let dy = [-1, 0, 1, -1, 1, -1, 0, 1];

let uniqueHeight = new Set();
let target = 0;
let result = 1e9;
let startX;
let startY;
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    uniqueHeight.add(height[i][j]);

    if (arr[i][j] === 'P') {
      startX = i;
      startY = j;
    }
    if (arr[i][j] === 'K') target += 1;
  }
}

uniqueHeight = [...uniqueHeight].sort((a, b) => a - b);
let left = 0;
let right = 0;
let middle = 0;
let cnt = 0;
for (let i = 0; i < uniqueHeight.length; i++) {
  if (uniqueHeight[i] === height[startX][startY]) {
    right = i;
    middle = i;
    break;
  }
}
let visited = [];
while (true) {
  while (true) {
    visited = [];
    cnt = 0;
    for (let i = 0; i < n; i++) visited.push(new Array(n).fill(false));

    dfs(startX, startY);
    if (right < uniqueHeight.length - 1 && cnt < target) right += 1;
    else break;
  }
  if (cnt === target) {
    result = Math.min(result, uniqueHeight[right] - uniqueHeight[left]);
  }
  left += 1;
  if (left > middle ) break;
}

console.log(result);

function dfs(x, y) {
  visited[x][y] = true;
  if (arr[x][y] === 'K') cnt += 1;
  for (let i = 0; i < 8; i++) {
    let nx = x + dx[i];
    let ny = y + dy[i];
    if (nx < 0 || nx >= n || ny < 0 || ny > n) continue;
    if (!visited[nx][ny]) {
      if (
        height[nx][ny] >= uniqueHeight[left] &&
        height[nx][ny] <= uniqueHeight[right]
      ) {
        dfs(nx, ny);
      }
    }
  }
}

 

문제는 배달을 하면서 각 지역마다 높이가 있는데, 배달을 하기 위해서 필요한 높이차의 최소값을 구하는 것 입니다.

3
P..
.KK
...
3 2 4
7 4 2
2 3 1

입력 예시는 위와 같은데, P는 시작점, K는 반드시 들려야하는 지점입니다.

이때 한상덕 씨는 대각선 및 좌우로 이동할 수 있으니 3에서 시작해서 4와 2를 방문하면 되니 답은 4-2 인 2가 나옵니다.

이를 알고리즘으로 구현할 때, 로직은 아래 순서 입니다.

1. 우선 입력값을 통해서, 각각의 유니크한 높이를 구한다. 이후 시작점을 찾고 시작점의 높이를 구합니다.

2. 투포인터 개념으로 접근할 건데, 유니크한 높이를 구한 배열에서 좌측포인터는 0, 우측포인터는 시작점의 높이 인댁스를 구합니다. 

3. 이후 dfs를 통하여서, 각각의 지점에 포인터의 높이 범위 내의 있는 경우 방문을 진행합니다. 그리고 만약 방문 지점이 타겟 숙소인 경우 count를 올려줍니다. 

4. 이때 count가 목표숙소 수보다 작다면, 높이 범위가 맞지 않아서 방문 못하는 것이기 때문에 우측포인터의 index를 증가시켜줍니다.

5. 이후 방문이 완료되면(count와 타겟수가 같다면)  우측 index값은 고정시킵니다.

6. 이후 좌측 포인터를 이동시켜서 좌측 포인터의 최소값을 찾습니다.

 

즉 위 문제는 투 포인터와 dfs 로직이 섞여 있습니다.

하나하나 해석하면

 

STEP1 

const fs = require('fs');
const input = fs
  .readFileSync(__dirname + '/input.txt')
  .toString()
  .split('\n');

const n = +input[0];
const arr = [];
for (let i = 1; i <= n; i++) {
  arr.push(input[i].split(''));
}

const height = [];
for (let i = n + 1; i <= n + n; i++) {
  height.push(input[i].split(' ').map(Number));
}

let dx = [-1, -1, -1, 0, 0, 1, 1, 1];
let dy = [-1, 0, 1, -1, 1, -1, 0, 1];

1. 우선 입력값을 받고, 총 개수를 특정하고, 각각의 높이값과 위치에 대한 정보를 추출해서 배열에 담습니다.

2. dfs시에 배열 내에서 상하좌우대각선 이동을 하기에 dx,dy를 통해서 총 8방위를 담아줍니다.

 

STEP2

let uniqueHeight = new Set();
let target = 0;
let result = 1e9;
let startX;
let startY;
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    uniqueHeight.add(height[i][j]);

    if (arr[i][j] === 'P') {
      startX = i;
      startY = j;
    }
    if (arr[i][j] === 'K') target += 1;
  }
}

uniqueHeight = [...uniqueHeight].sort((a, b) => a - b);

 

1. 이후 높이값을 통해서 유니크한 높이값을 찾아줍니다. ( 포인터의 이동시에 중복된 높이는 필요없기 때문!)

2. 결과값은 우선 가능한 가장 큰 값을 할당 (1e9가 문제 제약 조건이었습니다)

3. 이후 반복문을 통해서 각각의 높으로 Set에 담고, K가 나오면 target 개수 증가, P가 나오면 시작점으로 기록

4. 마지막으로 완성된 Set을  배열로 바꾸고 오름차순으로 정렬 (오름차순이야지 포인터가 의미 있습니다)

 

STEP3

 

let left = 0;
let right = 0;
let middle = 0;
for (let i = 0; i < uniqueHeight.length; i++) {
  if (uniqueHeight[i] === height[startX][startY]) {
    right = i;
    middle = i;
    break;
  }
}
let cnt = 0;
let visited = [];
while (true) {
  while (true) {
    visited = [];
    cnt = 0;
    for (let i = 0; i < n; i++) visited.push(new Array(n).fill(false));

    dfs(startX, startY);
    if (right < uniqueHeight.length - 1 && cnt < target) right += 1;
    else break;
  }
  if (cnt === target) {
    result = Math.min(result, uniqueHeight[right] - uniqueHeight[left]);
  }
  left += 1;
  if (left > middle ) break;
}

console.log(result);

 

1. 방문 배열을 만들어줍니다. 방문 배열을 통해서 dfs로 각각의 좌측포인터와 우측포인터에 대한 탐색을 시작합니다.

2. 우측 포인터의 최소값은 시작점의 값으로 설정하고 중간지점을 설정합니다 ( 탈출 조건 용도로 중간지점 설정)

3. 이후 방문 배열(visited)과 횟수(cnt)를 선언합니다.

 

4. 반복문에서 dfs을 통해서 집에 도착할 경우 cnt를 증가시키고 작은 경우 right의 값을 증가, 최종적으로 cnt가 목표수와 같아지면 결과값(이전값과 비교해서 더 작으면)을 할당합니다.

5. 이후 left 값을 증가시킵니다 . 이때 초기 설정했던 middle까지만 확인하고 탈출 시킵니다.