BOJ 16173 - 점프왕 쩰리(small)

문제

백준 온라인 저지 - 16173번

풀이 과정

시작 지점에서 목표 지점까지의 도달 가능성 유무를 판단하는 문제입니다.

BFS 를 이용해서 각 칸의 이동력에 따라 탐색을 수행하면 됩니다.

코드

import sys
from collections import deque

N = int(input())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(sx, sy):
    q = deque()
    visit = [[0] * N for _ in range(N)]

    q.append([sx, sy])

    while q:
        x, y = q.popleft()
        if board[x][y] == -1:
            return True

        offset = board[x][y]
        for dir in range(4):
            nx, ny = x + dx[dir] * offset, y + dy[dir] * offset
            if 0 <= nx < N and 0 <= ny < N and not visit[nx][ny]:
                visit[nx][ny] = 1
                q.append([nx, ny])

    return False


def solution():
    is_reachable = bfs(0, 0)
    return 'HaruHaru' if is_reachable else 'Hing'


print(solution())