[백준|파이썬] 16173: 점프왕 쩰리 (Small) (실버4)

문제

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

16173번: 점프왕 쩰리 (Small)

 

 

🐍파이썬

메모리 초과된 코드

import sys
from collections import deque

n = int(sys.stdin.readline())
game = []
for _ in range(n):
    game.append(list(map(int, sys.stdin.readline().split())))

dy = [0, 1]
dx = [1, 0]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        for i in range(2):
            nx = x + dx[i] * game[x][y]
            ny = y + dy[i] * game[x][y]
            if nx >= n or ny >= n or nx < 0 or ny < 0:
                continue
            if game[nx][ny] == -1:
                return "HaruHaru"
            queue.append((nx, ny))
    return "Hing"

print(bfs(0, 0))

찾아보니 중복된 값이나 움직이지 않는 경우(game[nx][ny] == 0인 경우) queue에 들어가서 메모리 초과가 발생한다고 한다. 

메모리 초과를 해결하기 위해서는 위의 사항들에 대한 예외처리가 필요하다.

BFS

import sys
from collections import deque

n = int(sys.stdin.readline())
game = []
for _ in range(n):
    game.append(list(map(int, sys.stdin.readline().split())))
visited = [[0] * n for _ in range(n)]	#방문여부를 체크하기 위한 배열

dy = [0, 1]	#왼쪽, 아래로만 이동
dx = [1, 0]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = 1	#방문처리
    while queue:
        x, y = queue.popleft()
        for i in range(2):
            nx = x + dx[i] * game[x][y]	#game[x][y]의 값만큼 이동
            ny = y + dy[i] * game[x][y]
            if nx >= n or ny >= n or nx < 0 or ny < 0:	#배열의 값을 넘어선 경우 건너뛰기
                continue
            if visited[nx][ny] == 1:	#이미 방문한 경우 건너뛰기
                continue
            if game[nx][ny] == 0:	#움직이지 않는 경우 건너뛰기
                continue
            if game[nx][ny] == -1:	#목적지에 도달했을 경우 HaruHaru 리턴
                return "HaruHaru"
            #위의 예외에 해당하지 않는 경우 해당 위치로 이동
            queue.append((nx, ny))
            visited[nx][ny] = 1	#방문처리
    return "Hing"	#큐가 빌때까지 목적지에 도착하지 못한 경우 Hing 리턴

print(bfs(0, 0))	#(0,0)에서부터 시작