문제

‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.

‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.
‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.
‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.
‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.
‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다. 칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.
새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다. 하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다. ‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는 지 알아봐 달라고 부탁했다. ‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!

입력

입력의 첫 번째 줄에는 게임 구역의 크기 N (2 ≤ N ≤ 3)이 주어진다.

입력의 두 번째 줄부터 마지막 줄까지 게임판의 구역(맵)이 주어진다.

게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.

출력

‘쩰리’가 끝 점에 도달할 수 있으면 “HaruHaru”(인용부호 없이), 도달할 수 없으면 “Hing” (인용부호 없이)을 한 줄에 출력합니다.

예제 입력 1

3
1 1 10
1 5 1
2 2 -1

예제 출력 1

HaruHaru

쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다.

예제 입력 2

3
2 2 1
2 2 2
1 2 -1

예제 출력 2

Hing

쩰리는 맨 왼쪽 위의 칸에서 출발하더라도 절대 게임의 승리 지점인 (3, 3)에 도달할 수 없다.

나의 코드

let input = require("fs")
  .readFileSync("example.txt")
  .toString()
  .trim()
  .split("\n")
  .map((row) => row.split(" ").map(Number));
input.shift();

// 이미 방문해본 곳을 마킹할 map을 선언. (input과 크기가 같은 2차원 배열)
let map = [...Array(input[0].length)].map((_) =>
  [...Array(input[0].length)].map((v) => (v = 0))
);
function solution(board) {
// 시작점은 [0, 0] 좌표이다.
  let [x, y] = [0, 0];
// 최단 거리를 구하기 위해 bfs로 풀기로 함.
  function bfs(x, y) {
  // 방문 가능한 좌표를 queue에 push하기 위해 빈 queue 선언
    let queue = [];
    // 첫 시작 때 [0, 0] push
    queue.push([x, y]);

// 마지막 지점에 도착할 수 있는지 판가름날 때까지 while문 반복
    while (true) {
    // 도착 지점 마지막 숫자에 비로소 마킹이 되었을 때 "HaruHaru" 반환
      if (map[map.length - 1][map.length - 1] > 0) return "HaruHaru";
      // 도착 지점 마지막 숫자에 비로소 마킹이 안 되었는데 queue의 길이가 0이면 더 이상 갈 수 있는 // 곳이 없다는 의미이므로 "Hing" 반환
      if (queue.length === 0) return "Hing";

 // queue에서 다음 순서인 좌표 꺼내옴
      [x, y] = queue.shift();

// 오른쪽 또는 아래쪽만 방문 가능하므로 좌표 하나당 for문을 2번 돌림.
      for (let i = 0; i < 2; i++) {
      // for문에서 i가 0이면 오른쪽으로 가려고 시도, 1이면 아래쪽으로 가려고 시도
        let [nx, ny] = i === 0 ? [x, y + board[x][y]] : [x + board[x][y], y];
    // 지옥의 if문 시작. board 밖으로 빠져나가면 continue
        if (nx < 0 || ny < 0 || nx >= board.length || ny >= board.length)
          continue;
        // 이미 가본 곳이면 continue
        if (map[nx]?.[ny] > 0) continue;
        // map에 방문 처리
        map[nx][ny] = map[x][y] + 1;
     // 방문 가능한 좌표이므로 queue에 push
        queue.push([nx, ny]);
      }
    }
  }
  return bfs(x, y);
}
console.log(solution(input));

요즘 bfs 푸는 데 맛들린 것 같다. 2차원 배열에 숫자가 하나씩 새롭게 찍혀가는 걸 구경하는 재미가 있달까?! ㅋㅋㅋㅋㅋ 물론 골드 문제는 아직 어렵다..ㅎㅎ
그래도 한달 전의 나였다면 쳐다도 못 볼 문제였지만 풀어냈다는 사실만으로도 한 문제 풀어낼 때마다 기쁘다!!
이번 주말부터는 DP를 시작해보는 걸루!! 어려울까봐 좀 긴장되지만 차근차근 하나씩 해보자 쟤스민 화이팅!!