[Python][BoJ] 점프왕 쩰리 (Large)

 

🫡 Overview

체감 난이도: ★☆☆☆☆

소요시간: 40분

문제 레벨: 실버1 / 문제 유형: BFS
풀이 상태:  스스로 해결
추후: 다시 풀어보기

 

---

문제 링크

https://www.acmicpc.net/problem/16174

 

요구사항 분석

"""
목적: 주어진 이동 조건에 따라서 쩰리가 우승할 수 있는지 알아보기
점프
- 시작점(0,0)
- 이동 조건
  - 이동 방향: 오른쪽(0,+1) or 아래 (-1,0)
  - 이동 크기: 현재 밟고 있는 칸의 수 만큼 (0~100)
  - 이동 제한: NxN 맵 밖으로 나가면 안됨.
승리 조건: (N-1,N-1)로 도달

입력:
- N(2<= N <= 64)
- NxN 크기의 맵
  - 승리 지점: -1, 나머지는 0~100의 정수
출력: 우승할 수 있으면 HaruHaru, 아니면 Hing
"""

 

나의 코드

간단한 BFS 알고리즘으로 풀었다. 이런 문제들은 안될 때를 걸러내는 것이 힘든 것 같다. 

• 처음에는 While True 문을 계속 반복하면서 도착지에 가면 우승, 아니면 실패 이렇게 풀려고 했는제 while 문 종료 조건이 생각나지 않음. 
• 그래서 queue를 활용하여 queue가 빌 때까지 탐색하는 것으로 바꿨다. 

from collections import deque

# 입력 받기
N = int(input()) #  2<= N <= 64
board = [list(map(int, input().split())) for _ in range(N)] # NxN 크기의 게임맵

def out_of_range(x,y):
    if x<0 or x>=N or y<0 or y>=N:
        return True
    return False

def check(N, board) -> bool:
    answer = False
    queue = deque()
    queue.append((0, 0))
    visited = [[False]*N for _ in range(N)]
    visited[0][0] = True
    d_lst = [(0,+1),(+1,0)] # 오른쪽, 아래 이동
    while queue: # 큐가 빌 때까지
        x,y = queue.popleft()
        if x == N-1 and y == N-1:
            answer = True
            break
        for dx,dy in d_lst:
            amount = board[x][y]
            nx, ny = x+(dx*amount), y+(dy*amount)
            if not out_of_range(nx,ny) and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx,ny))
    return answer

result = check(N,board)
if result: print("HaruHaru")
else: print("Hing")

 

---

배운 점/느낀 점

- DP 유형이라는데, 왜 DP일까욥?

- 문제 분석하는데 시간이 너무 오래 걸린다!!! 

 

 

---