백준 16174번 - 점프왕 쩰리 (Large)

점프왕 쩰리 (Large) 문제 바로 가기

풀이 날짜: 2026-03-21

baekjoon 알고리즘 문제 풀이

풀이 코드


from collections import deque
import sys
input = sys.stdin.readline

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

q = deque()
q.append((0,0))
visited[0][0] = True

while q:
    x,y = q.popleft()

    if graph[x][y] == -1:
        print("HaruHaru")
        exit()

    jump = graph[x][y]

    nx = x + jump
    ny = y
    if 0 <= nx < n and not visited[nx][ny]:
        visited[nx][ny] = True
        q.append((nx,ny))

    nx = x
    ny = y + jump
    if 0 <= ny < n and not visited[nx][ny]:
        visited[nx][ny] = True
        q.append((nx, ny))

print("Hing")

문제 접근

이 문제는 단순한 그래프 탐색 문제가 아니라, 각 칸에 적힌 숫자만큼 이동하는 ‘점프형 탐색’ 문제이다. 시작 위치는 (0,0)이며, 현재 위치에서 오른쪽 또는 아래 방향으로 이동할 수 있다. 단, 한 칸씩 이동하는 것이 아니라 현재 위치의 값만큼 한 번에 점프해야 한다. 최종적으로 -1이 적힌 위치에 도달할 수 있는지 판단하는 것이 목표이다.

핵심 아이디어

처음에는 일반적인 BFS처럼 상하좌우 한 칸씩 이동하는 방식으로 접근하려 했지만, 문제의 핵심은 “이동”이 아니라 “점프”라는 점을 깨닫는 것이 중요했다. 따라서 각 위치에서 이동 가능한 좌표는 (x + k, y) 또는 (x, y + k) 두 가지로 제한된다. 이 특성을 반영하여 BFS를 구성하면 된다.

시행착오

초기에는 dx, dy 배열을 사용하여 한 칸씩 이동하는 방식으로 코드를 작성했지만, 이는 문제의 요구사항과 맞지 않았다. 또한 방문 처리를 위해 visited[nx][ny] += 1과 같은 방식으로 값을 증가시키는 실수를 했는데, 이 문제에서는 단순히 방문 여부만 확인하면 되기 때문에 boolean 형태로 처리하는 것이 더 적절하다.

해결방법

큐를 활용한 BFS를 사용하여 시작점부터 탐색을 진행한다. 현재 위치를 꺼낸 뒤, 해당 위치의 값을 이용해 이동할 수 있는 두 좌표를 계산한다. 이동 가능한 범위 내에 있고 아직 방문하지 않은 경우에만 큐에 추가하며, 이 과정을 반복한다. 탐색 도중 -1에 도달하면 “HaruHaru”를 출력하고, 끝까지 도달하지 못하면 “Hing”을 출력한다.

탐색 흐름

BFS의 while 루프 내부에서는 세 가지 작업이 반복된다. 먼저 큐에서 현재 위치를 꺼내고, 그 위치의 점프 값을 확인한다. 이후 아래 방향과 오른쪽 방향으로 점프한 새로운 위치를 계산한다. 해당 위치가 유효하고 방문하지 않은 경우에만 큐에 추가하여 탐색을 이어간다. 이 과정을 통해 가능한 모든 경로를 탐색하게 된다.

핵심 포인트

이 문제의 핵심은 “한 칸 이동 BFS”가 아니라 “값 기반 점프 BFS”라는 점이다. 단순히 인접한 칸으로 이동하는 것이 아니라, 현재 칸의 값에 따라 이동 범위가 결정되기 때문에 dx, dy를 사용하는 일반적인 BFS 방식과는 다르게 접근해야 한다. 또한 중복 탐색을 방지하기 위한 방문 체크가 필수적이다.

느낀점

이 문제를 통해 BFS라고 해서 항상 동일한 형태로 적용되는 것이 아니라, 문제 조건에 맞게 탐색 방식 자체를 변형해야 한다는 점을 배울 수 있었다. 특히 “이동 방식”을 정확히 이해하지 못하면 완전히 다른 문제로 접근하게 된다는 점에서, 문제 해석의 중요성을 다시 한 번 느낄 수 있었다.

Vienna sausage