[백준] 16173번: 점프왕 쩰리 (Small) - Python

링크: https://www.acmicpc.net/problem/16173

 

아이디어

• 가장 빠르게 목적지에 가능한 경우가 있는지 확이해야하기 때문 BFS진행
• 방문 확인용 배열 사용
• bfs 진행 중 목적지에 도착시 바로 탐색 종료 후 "HaruHaru" 출력
• 탐색이 완료된 후에도 목적지에 도착하지 못할시 "Hing" 출력

 

구현

# (0,0) 출발
# 범위 안에서만 이동
# 오른쪽 아래로만 이동 가능
# 가장 오른쪽 가장 아래 도착 = 승리
# 이동가능 수는 밟고있는 칸의 수 만큼 무조건 이동

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


def bfs(i, j):
    q = deque()
    q.append((i, j))
    visited = [[False]*N for _ in range(N)]
    visited[i][j] = True

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

        if y == N-1 and x == N-1:
            return True 

        if game[y][x] <= 0:
            continue

        ny = y + game[y][x]
        if ny < N and not visited[ny][x]:
            visited[ny][x] = True
            q.append((ny, x))

        nx = x + game[y][x]
        if nx < N and not visited[y][nx]:
            visited[y][nx] = True
            q.append((y, nx))

    return False


N = int(input())

game = [list(map(int, input().split())) for _ in range(N)]


if bfs(0, 0):
    print("HaruHaru")
else:
    print("Hing")

 

마무리

뭔가 문제가 좀 이상했다. 한번에 오른쪽아니면 아래쪽으로만 이동 해야한다는 조건이 없는거 같은데 그렇게 이해하고 풀어야 풀어지더라.. 흠 내가 이해력이 딸리는지 이번 문제도 헛다리 짚다가 시간만 날렸다..