[정글 알고리즘] - [하] - 백준 16173 - 점프왕 쩰리 (Small)- 실버 4

이 문제는 코드보다 먼저 문제 상황을 정확히 해석하는 것이 더 중요하다. 현재 칸에 적힌 숫자만큼 오른쪽 또는 아래로 점프하면서, 오른쪽 아래 끝 칸에 도달할 수 있는지를 판단하는 문제다. [Source](https://www.acmicpc.net/problem/16173)

문제 요약

N × N 게임판이 주어지고, 시작 위치는 항상 왼쪽 위 칸이다. 현재 밟고 있는 칸의 숫자를 보고 그 수만큼 오른쪽 또는 아래로 이동할 수 있다. 마지막 칸에는 -1이 적혀 있고, 그곳에 도달하면 성공이다. 

항목	내용
시작 위치	(0, 0)
이동 방향	오른쪽, 아래만 가능
이동 거리	현재 칸 숫자만큼 정확히 이동
목표	오른쪽 아래 끝 칸(-1)에 도달 가능하면 HaruHaru, 아니면 Hing

이 문제에서 제일 중요한 해석

많은 사람이 처음에 헷갈리는 부분이 바로 이거다. 한 칸씩 움직이는 문제가 아니다.

예를 들어 현재 칸 값이 3이면

오른쪽 1칸 ❌

오른쪽 2칸 ❌

오른쪽 3칸 ⭕

아래 3칸 ⭕

즉, 숫자는 “몇 칸 점프할 수 있는가”를 뜻하며, 그 수보다 적게 또는 많이 움직일 수 없다. [Source](https://www.acmicpc.net/problem/16173)

좌표 해석도 정확해야 한다

좌표는 (행, 열) 기준으로 생각하면 된다.

아래로 이동

행(row)이 증가한다.

(r + jump, c)

오른쪽으로 이동

열(col)이 증가한다.

(r, c + jump)

예시

현재 위치가 (0, 0) 이고 값이 3이라면

아래 → (3, 0)

오른쪽 → (0, 3)

작은 예시로 문제 감 잡기

아래와 같은 보드가 있다고 해보자.

2	5	1
6	1	1
1	1	-1

시작 위치는 (0,0)이고 값은 2다. 그러면 갈 수 있는 곳은 딱 두 군데다.

아래 → (2, 0)

오른쪽 → (0, 2)

이런 식으로 각 칸에서 다음 후보를 계산하면서, 최종적으로 -1에 도달할 수 있는지를 보면 된다.

왜 DFS/BFS 문제일까?

각 칸에 도착할 때마다 항상 선택지가 생긴다.

1. 아래로 점프

2. 오른쪽으로 점프

즉, 현재 위치에서 갈 수 있는 다음 위치들을 따라 계속 탐색하다가, 어느 한 경로에서라도 끝 칸 -1에 도달하면 성공이다. 이런 구조는 그래프 탐색과 똑같기 때문에 DFS나 BFS로 풀 수 있다.

이 문제에서 자주 헷갈리는 포인트

헷갈리는 부분	정리
한 칸씩 움직이는 줄 아는 경우	현재 칸 숫자만큼 정확히 점프해야 한다
왼쪽, 위쪽도 갈 수 있다고 생각하는 경우	오른쪽과 아래만 가능하다 [Source](https://www.acmicpc.net/problem/16173)
최소 점프 횟수를 구해야 한다고 생각하는 경우	도달 가능 여부만 판단하면 된다
범위 밖 좌표도 그대로 탐색하는 경우	배열 범위 체크가 반드시 필요하다

DFS로 풀 때 필요한 판단은 3가지

1. 지금 위치가 목표인가?

board[r][c] == -1

2. 다음 위치가 범위 안인가?

r + jump < n

c + jump < n

3. 이미 방문한 칸인가?

visited[r][c]

DFS 아이디어를 코드로 바꾸면

현재 위치를 (r, c)라고 하면, 현재 칸의 값은 이렇게 가져온다.

jump = board[r][c]

그 다음 갈 수 있는 후보 좌표는 두 개다.

아래 → (r + jump, c)

오른쪽 → (r, c + jump)

다만, 여기서 바로 재귀 호출하면 안 되고 두 가지를 먼저 체크해야 한다.

1. 배열 범위 안인지

2. 아직 방문하지 않은 칸인지

visited가 왜 필요한가?

이 문제는 오른쪽과 아래만 이동하므로 겉보기에는 단순해 보이지만, 실제 구현에서는 같은 칸을 여러 번 탐색할 수 있다. 그래서 이미 확인한 칸을 다시 탐색하지 않도록 방문 체크를 해두는 편이 안전하다.

visited = [[False] * n for _ in range(n)]

그리고 DFS에 들어온 순간

visited[r][c] = True

DFS 흐름 한 번에 보기

1단계

현재 칸이 -1이면 바로 성공

2단계

현재 칸 방문 처리

3단계

점프 거리 jump 가져오기

4단계

아래/오른쪽으로 갈 수 있으면 재귀 탐색

5단계

둘 다 실패하면 False 반환

정답 코드 (DFS)

def dfs(r, c, visited):
    if board[r][c] == -1:
        return True

    visited[r][c] = True
    jump = board[r][c]

    if r + jump < n and not visited[r + jump][c]:
        if dfs(r + jump, c, visited):
            return True

    if c + jump < n and not visited[r][c + jump]:
        if dfs(r, c + jump, visited):
            return True

    return False


n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

if dfs(0, 0, visited):
    print("HaruHaru")
else:
    print("Hing")

코드에서 꼭 기억할 포인트

포인트	이유
board[r][c] == -1을 먼저 체크	도착 즉시 성공 처리해야 함
jump = board[r][c]	현재 칸의 숫자가 이동 거리이기 때문
범위 체크 후 재귀 호출	배열 밖으로 나가면 에러 발생
재귀 결과가 성공일 때만 True 반환	무조건 True를 반환하면 잘못된 경로도 성공으로 처리됨

한 줄로 정리하면

이 문제는 현재 칸 숫자만큼 오른쪽 또는 아래로 점프하면서, 끝 칸(-1)에 도달 가능한지 DFS로 확인하는 문제다. 문제를 처음 읽을 때 가장 중요한 건 “한 칸 이동이 아니라 숫자만큼 점프”라는 점을 정확히 이해하는 것이다.

마무리

이 문제는 알고리즘 자체보다도 문제 해석이 먼저다. 이동 규칙을 정확히 이해하고 나면, 결국 각 칸에서 아래와 오른쪽 두 방향으로만 뻗어나가는 탐색 문제라는 걸 알 수 있다.

처음엔 좌표와 점프 개념이 헷갈릴 수 있지만, (r + jump, c), (r, c + jump) 이 두 식만 정확히 잡으면 훨씬 쉬워진다.

즉, 이 문제의 핵심은 복잡한 구현이 아니라 문제를 올바르게 읽는 것이다.