백준 알고리즘 - 16173 - 점프왕 쩰리 (Small) - 그래프 문제 풀이

• 문제 링크:
  https://www.acmicpc.net/problem/16173
• 난이도: 실버 4

끝점 -1에 도달할 수 있는지, 없는지를 알기 위해 모든 이동 경로를 탐색해야 하므로 그래프+브루트포스 방법을 써야 했습니다.

그래프 문제치고 난이도가 낮은 문제로, 상하좌우 네 방향이 아닌 오른쪽 또는 아래로만 이동할 수 있고 무조건 0, 0에서 시작하는 조건이어서 단순하게 풀 수 있었습니다.

 

끝점에 도달한다는 특수한 상황일 때 출력 값이 다르므로, answer의 디폴트를 Hing로 두고 DFS 로직을 구현했습니다.

let [size, ...map] = `${require('fs').readFileSync('/dev/stdin')}`.trim().split(/\n/);

size = +size;
map = map.map(v => v.split(" ").map(Number));

const visited = Array.from({length: size}, () => new Array(size).fill(false));
const stack = [];
let answer = 'Hing';

stack.push([0, 0]);

while (stack.length > 0) {
    const [x, y] = stack.pop();

    // 이미 방문한 곳이면 패스
    if (visited[x][y]) continue;

    visited[x][y] = true;
    const distance = map[x][y];

    if (distance === -1) {
        answer = 'HaruHaru';
        break;
    }

    const newX = x + distance;
    const newY = y + distance;

    if (newX < size) {
        stack.push([newX, y]);
    }
    if (newY < size) {
        stack.push([x, newY]);
    }
}

console.log(answer);