백준_세 번 이내에 사과를 먹자_26169

세 번 이내에 사과를 먹자

문제

5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 보드의 격자는 사과가 1개 있는 격자, 장애물이 있는 격자, 빈칸으로 되어 있는 격자로 구분된다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c는 열 번호를 나타낸다. 행 번호는 맨 위 위치가 0이고 아래 방향으로 1씩 증가한다. 열 번호는 맨 왼쪽 위치가 0이고 오른쪽으로 1씩 증가한다. 즉, 맨 왼쪽 위 위치가 (0, 0), 맨 아래 오른쪽 위치가 (4, 4)이다.

현재 한 명의 학생이 (r, c) 위치에 있고 한 번의 이동으로 상, 하, 좌, 우 방향 중에서 한가지 방향으로 한 칸 이동할 수 있다. 학생이 사과가 있는 칸으로 이동하면 해당 칸에 있는 사과를 1개 먹는다. 장애물이 있는 칸으로는 이동할 수 없다. 학생이 지나간 칸은 학생이 해당 칸을 떠나는 즉시 장애물이 있는 칸으로 변경된다. 즉, 학생이 해당 칸에서 상, 하, 좌, 우 방향으로 한 칸 이동하는 즉시 해당 칸은 장애물이 있는 칸으로 변경된다.

학생이 현재 위치 (r, c)에서 세 번 이하의 이동으로 사과를 2개 이상 먹을 수 있으면 1을 출력하고, 그렇지 않으면 0을 출력하자.

입력

첫 번째 줄부터 다섯 개의 줄에 걸쳐 보드의 정보가 주어진다. i번째 줄의 j번째 수는 보드의 (i - 1)번째 행, (j - 1)번째 열의 정보를 나타낸다. 보드의 정보가 1이면 해당 칸은 사과가 1개 있는 격자임을 나타내고, 0이면 빈칸이 있는 격자를 나타내고, -1이면 장애물이 있는 격자임을 나타낸다.

다음 줄에 학생의 현재 위치 r, c가 빈칸을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄에 학생이 현재 위치 (r, c)에서 세 번 이하의 이동으로 사과를 2개 이상 먹을 수 있으면 1을 출력하고, 먹을 수 없으면 0을 출력한다.

예제 입력

0 0 1 0 0
0 0 -1 0 0
0 0 1 0 0
1 1 -1 1 0
0 0 0 -1 0
4 1

예제 출력

1

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const board = [];
for (let i = 0; i < 5; i += 1) board.push(input[i].split(' ').map(Number));
const [r, c] = input[5].split(' ').map(Number);

const dxdy = [
  [-1, 0],
  [0, -1],
  [1, 0],
  [0, 1],
];

let answer = 0;
const visited = Array.from({ length: 5 }, () => new Array(5).fill(false));

const dfs = (x, y, apple, move) => {
  // 이동 횟수가 3번 초과이거나 현재 사과 수가 2개 이상인 경우
  if (move === 0 || apple >= 2) {
    if (apple >= 2) answer = 1;
    return;
  }
  for (const [dx, dy] of dxdy) {
    const [nx, ny] = [x + dx, y + dy];
    // 범위 벗어나는 경우
    if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5 || board[nx][ny] === -1)
      continue;
    // 방문하지 않은 위치인 경우
    if (!visited[nx][ny]) {
      visited[nx][ny] = true;
      dfs(nx, ny, apple + (board[nx][ny] === 1 ? 1 : 0), move - 1);
      visited[nx][ny] = false;
    }
    if (answer) return;
  }
  return;
};

visited[r][c] = true;
dfs(r, c, 0, 3);

console.log(answer);

풀이 및 해설

• 학생이 현재 위치에서 세 번 이하의 이동으로 사과 2개 이상을 먹을 수 있는지 확인
  • 상, 하, 좌, 우 방향으로 한 번 이동 가능
  • 장애물 있는 칸은 이동 불가
  • 학생이 지나간 칸은 장애물 있는 칸으로 변경됨
• DFS로 풀이
  1. 현재위치(r, c)에서 상, 하, 좌, 우로 이동 가능한지 파악
  2. 이동 가능하면 현재 위치 장애물 칸으로 변경 후 이동 시킴(이동 횟수 감소)
  3. 이동된 칸에 1(사과)이 존재하면 사과 카운트 증가
  4. 이동 횟수가 3을 초과하면 해당 DFS 수행 중지