[Python]백준_16173 : 점프왕 쩰리 (Small)

2023년 1월 14일에 작성됨

 

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

16173번: 점프왕 쩰리 (Small)

 

 

문제 분석

너비 우선 탐색 BFS 알고리즘을 이용하여 문제를 풀 수 있다.

 

 

소스 코드 (⭕)

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


n = int(input())  # 게임 구역의 크기 n 입력

board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

visit = []
# 방문 여부 체크 (초깃값 False로 설정)
for _ in range(n):
    visit.append([False]*n)

# 오른쪽과 아래에 대한 방향 설정
dx = [1, 0]
dy = [0, 1]

# 너비 우선 탐색(BFS) 알고리즘 함수 정의
def bfs(x, y, visit):
    queue = deque()
    queue.append((x, y))
    visit[x][y] = True

    while queue:
        x, y = queue.popleft()
        # 맨 오른쪽 아래에 도달하면 HaruHaru 출력
        if board[x][y] == -1:
            return 'HaruHaru'

        jump = board[x][y]
        # 오른쪽과 아래 탐색
        for i in range(2):
            # 좌표에 대한 이동은 기존 x, y 값에 점프값과 방향값을 곱하여 이동
            nx = x+dx[i]*jump
            ny = y+dy[i]*jump
            # 범위 안에 있고, 방문하지 않았으면 방문 체크 후 queue에 넣기
            if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0:
                visit[nx][ny] = True
                queue.append((nx, ny))
    return 'Hing'


print(bfs(0, 0, visit))

 

코드 분석

1. 게임 구역의 크기 n을 입력받고, n만큼 게임판의 맵을 입력받는다.

2. 방문 여부를 체크하기 위해 n개의 리스트 요소의 초깃값을 false로 설정해준다.

3. 이동 방향을 설정해주기 위해 dx와 dy의 좌표값을 선언해준다.

4. 큐를 사용하여 해당 x, y 좌표를 넣고, 그 좌표를 true로 방문 처리를 해준다.

5. x, y 값을 덱을 이용하여 삭제해주고, if문으로 게임판의 지점이 -1이라면 'HaruHaru'를 반환해준다.

6. 도착 칸의 수만큼 점프를 하기 위해 jump 변수에 현재 지점의 값을 넣어준다.

7. 이동한 좌표 (nx, ny) 를 구하기 위해 현재 위치 (x, y)와 방향 값인 (dx, dy)에 점프할 값인 jump를 곱한 것을 더해준다.

8. 만약, 이동한 좌표 nx, ny가 범위 안에 있고, 방문하지 않은 지점이라면 True로 방문 처리를 해주고 큐에 좌표를 넣어준다.

9. 큐가 참일때까지 반복해주어 if문에 걸리지 않는다면 'Hing'을 반환해준다.

10. (x, y)를 출발점인 (0, 0)으로 하고, n만큼의 크기인 visit을 매개변수로 하는 bfs 함수를 호출하여 그 반환값을 출력한다.

 

 

 

end

문제가 길고 어려워서 포스팅을 계속 미뤘던 문제...ㅠㅠ
결국 하긴 했는데 힘들지만 뿌듯하다!!
코드 분석 왜케 길어ㅋㅋㅋ🤣