[BFS] 16173번 - 점프왕 쩰리 (Small) - python, 실버4

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

16173번: 점프왕 쩰리 (Small)

 

 

예전에 공부할땐 일단 외우고 어떻게 응용할지에 대해 초점을 맞췄었는데

그러다보니 실력이 잘 안느는것 같아서 차근차근 어떻게 풀지 생각하는 연습을 하고자 쉬운 문제부터 풀기 시작했다.

 

 

 

문제

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

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

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

입력

입력의 첫 번째 줄에는 게임 구역의 크기 N (2 ≤ N ≤ 3)이 주어진다.

입력의 두 번째 줄부터 마지막 줄까지 게임판의 구역(맵)이 주어진다.

게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.

출력

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

 

 

---

 

 💡 사고 과정

1. 오른쪽, 아래쪽으로 갈수밖에 없고, 왼쪽상단에서 출발해 오른쪽하단에 도달하는지 여부만 확인하면 되는 문제이다. 
2. bfs를 이용해야겠다 생각했다.
3. d = [[1,0],[0,1]] 로 두방향으로만 이동할 수 있기 때문에 2가지 방향의 상대값을 만들었다. 
4. while 큐에 값이 있을 동안 반복한다.
5. 큐에서 r,c를 빼고 해당 위치가 현재 쩰리가 위치한 존재라고 했을 때, 해당위치의 값이 -1인지 체크해준다. (-1이면 도착위치에 도달한것이다!)
6. 현재 위치에서 무조건 이동해야하는 칸수 move가 존재했다. 한 방향으로 이동하면 나머지 방향에 대한 상대값은 0이므로  쿨하게 move를 곱해서 이동할 좌표값인 dr, dc를 만들었다.
7. 만들어진 좌표가 유효한지 체크하고,
8. 유효하면 큐에 넣어준다. 

 

 

💻 메모리 초과 코드

#점프왕 젤리 16173 bfs
from collections import deque

import sys
input = sys.stdin.readline

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

d = [[1,0],[0,1]] #아래, 오른쪽

queue = deque()
queue.append([0,0])

flag = False

while(queue):
    r, c = queue.popleft()
    
    if(maps[r][c] == -1):
        flag = True
        break
    # r,c는 현재위치 
    move = maps[r][c] #현재위치에서 무조건 이동해야하는 칸수

    for i in range(2):
        dr = r+ d[i][0] * move
        dc = c+ d[i][1] * move
        
        if(0>dr or dr >= n or 0>dc or dc >= n):
            continue
        
        queue.append([dr,dc])


if flag: print("HaruHaru")
else : print("Hing")

visited를 만들어줄 필요가 없다고 생각했다. 

게임 구역의 크기 N (2 ≤ N ≤ 3)가 최대 3이라서, 3*3은 9칸짜리 작은 맵이었고,,

queue에 값이 들어가봤자.. 몇번이나 들어가겠어...? 

 

1 초 (추가 시간 없음)

128 MB

방문처리 여부에 따라서 메모리 초과가 나는 이유가 뭘까..

메모리제한은 128MB라서 굳이 방문처리 안해줘도 초과가 날 수 없을텐데....

다른 문제가 있나? 음 모르겠다.. 

 

 

⏺  디테일을 못잡아서 발생한 문제다! 🥹🥹🥹🥹🥹

게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.

게임판에 0이 들어있는 곳에 도달했을 때, 방문처리코드나, 0일경우 넘어가는 코드를 넣어주지 않으면 계속 같은 위치를 큐에 넣게 된다. 

따라서 메모리 초과가 발생하는것...!

 

나는 멍청이다 더 열심히하자... 🥲 

 

 

 

💻 정답 코드

 

✔️ 방문처리를 통한 해결

#점프왕 젤리 16173 bfs
from collections import deque

import sys
input = sys.stdin.readline

n = int(input())
maps = [ list(map(int,input().split())) for _ in range(n)]
visited = [[False]*n for _ in range(n)]

d = [[1,0],[0,1]] #아래, 오른쪽

queue = deque()
queue.append([0,0])

flag = False

while(queue):
    r, c = queue.popleft()
    
    move = maps[r][c]
    
    if(move == -1):
        flag = True
        break

    for i in range(2):
        dr = r+ d[i][0] * move
        dc = c+ d[i][1] * move
        
        if(0>dr or dr >= n or 0>dc or dc >= n):
            continue
        
        if not visited[dr][dc]:
            queue.append([dr,dc])
            visited[dr][dc] = True

if flag: print("HaruHaru")
else : print("Hing")

 

✔️ 0 따로 처리해주며 해결

from collections import deque

import sys
input = sys.stdin.readline

n = int(input())
maps = [ list(map(int,input().split())) for _ in range(n)]
visited = [[False]*n for _ in range(n)]

d = [[1,0],[0,1]] #아래, 오른쪽

queue = deque()
queue.append([0,0])

flag = False

while(queue):
    r, c = queue.popleft()

    move = maps[r][c] #현재위치에서 무조건 이동해야하는 칸수
    
    if move == 0:
        continue
    if move == -1:
        flag = True
        break

    for i in range(2):
        dr = r+ d[i][0] * move
        dc = c+ d[i][1] * move
        
        if(0>dr or dr >= n or 0>dc or dc >= n):
            continue
        
        queue.append([dr,dc])


if flag: print("HaruHaru")
else : print("Hing")

 

 

 

 

thanks to 명범님, 노을님 🥹