[백준 16174번] 파이썬 - 점프왕 쩰리(Large)

백준 16174 - 점프왕 쩰리

시간 제한 2초, 메모리 제한 128MB

# 조건

• ‘쩰리’는 점프하는 것을 좋아하는 젤리다.
• 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.
  1. ‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.
  2. ‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다.
     • 다른 출발점에서는 출발하지 않는다.
  3. ‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다.
     • 위쪽과 왼쪽으로는 이동할 수 없다.
  4. ‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.
  5. ‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다.
     • 칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.
• 새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다.
• 하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다.
• ‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는 지 알아봐 달라고 부탁했다.
• ‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!

입력

• 입력의 첫 번째 줄에는 게임 구역의 크기 N (2 ≤ N ≤ 64)이 주어진다.
• 입력의 두 번째 줄부터 마지막 줄까지 게임판의 구역(맵)이 주어진다.
• 게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.

출력

• ‘쩰리’가 끝 점에 도달할 수 있으면 “HaruHaru”(인용부호 없이), 도달할 수 없으면 “Hing” (인용부호 없이)을 한 줄에 출력합니다.

# 접근 방법

• bfs를 이용하여 풀어주었다.
• 문제를 풀며 이해하지 못했던 점은, 점프를 하기 때문에 2칸 이동이 아래 한 칸, 오른쪽 한 칸이 아니라 아래로 2칸 or 오른쪽으로 2칸이라는 점이다.
• bfs를 돌리며 아래 2가지를 체크해주면 된다.
  • (x좌표 + 점프할 칸 수, y좌표)이 범위 내에 존재
  • (x좌표, y좌표 + 점프할 칸 수)이 범위 내에 존재
  • 방문 여부
• 위의 조건을 만족한다면 방문 표시와 q에 담아준다.
• 도착지에 도착하였다면 출력 형식에 맞춰서 출력해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def bfs():  
    q = deque()  
    q.append((0, 0))  
    visited[0][0] = True  
    while q:  
        si, sj = q.popleft()  
        if (si, sj) == (N-1, N-1):  
            return  
        val = arr[si][sj]  
        # 현재 좌표에서 가야되는 거리가 도착점을 넘어선다면 continue  
        ni, nj, ci, cj = si + val, sj, si, sj + val  
        if 0<=ni<N and 0<=nj<N and not visited[ni][nj]:  
            q.append((ni, nj))  
            visited[ni][nj] = True  
        if 0<=ci<N and 0<=cj<N and not visited[ci][cj]:  
            q.append((ci, cj))  
            visited[ci][cj] = True  

N = int(input())  
arr = [[*map(int, input().split())] for _ in range(N)]  
visited = [[False] * N for _ in range(N)]  
bfs()  
print('HaruHaru' if visited[N-1][N-1] else 'Hing')

• 다른 분의 풀이를 참고하면서 잊고 지냈던 try, except을 볼 수 있었다.
• 범위 체크를 일일이 해주는 것이 아닌 점프 칸만큼 q에 담아준 후
  • try 배열에 방문
  • indexError 발생시 continue를 사용해주었다.

n=int(input())  
v=[[*map(int,input().split())]for _ in[0]*n]  
q=[(0,0)]  
while q:  
    x,y=q.pop(0)  
    try:  
        k=v[y][x]  
    except:  
        continue  
    v[y][x]=0  
    if k==-1:  
        print('HaruHaru');break  
    if k:  
        q.extend([(x+k,y),(x,y+k)])  
else:  
    print('Hing')