(Python/파이썬) - 백준(BOJ) 16173번 : 점프왕 쩰리 (Small)

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

 

이름이 ㅉㅔ리인데 깨져서 안나옵니다ㅠ 감안 부탁드릴게요

              ㄹ

16173번: 점프왕 쩰리 (Small)

---

• 문제 : 

‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.

 

1. ‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.
2. ‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.
3. ‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.
4. ‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.
5. ‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다. 칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.

 

새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다. 하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다. ‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는 지 알아봐 달라고 부탁했다. ‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!

 

 

 

---

• 풀이 :

bfs로 구현할 수 있는 문제였습니다.

 

알고리즘의 흐름입니다.

 

1. 시작점(0,0)을 담은 queue 선언

 

2. 시작점부터 탐색을 시작하며 x좌표와 y좌표에 board에서 이동할 수 있는 칸 수인 board[x][y]를 더하여 맵을 벗어나지 않는다면 queue에 넣어줌.

 

3. x좌표와 y좌표가 N-1에 도달한다면 오른쪽 가장 아래로 이동할 수 있는 것이므로 "HaruHaru" 출력, 아니라면 "Hing" 출력

 

 

주의할 점) board[x][y]가 0이라면 현재 좌표의 값을 무한정 queue에 넣게 되어 무한루프에 빠집니다.

따라서, board[x][y]의 값이 0일 경우 continue문으로 패스하였습니다. 

 

 

---

• 소스코드 : 

from collections import deque
N = int(input())
board = [list(map(int,input().split())) for _ in range(N)]
queue = deque()
queue.append([0,0])
while queue:
    x,y = queue.popleft()
    if board[x][y] == 0:
        continue
    if x == N-1 and y == N-1:
        print("HaruHaru")
        exit()
    if 0 <= x+board[x][y] < N and 0 <= y < N:
        queue.append([x+board[x][y],y])
    if 0 <= x < N and 0 <= y+board[x][y] < N:
        queue.append([x,y+board[x][y]])
print("Hing")