[Python] 16174번 점프왕 쩰리 (Large)

✏️ 문제

 

문제 파악

16173번 점프왕 쩰리 (Small) 와 비슷한 문제이다. 하지만 메모리가 매우 작습니다...... (메모리 초과 3번이나 떴다ㅠ)

 

메모리 초과를 해결한 방법은 다음과 같다.

• visited 배열을 없애고 graph 배열로만 방문했는 지 구분했다.
• 이미 방문했던 위치는 또 돌 필요가 없으므로 바로 continue를 통해 메모리를 절약하도록 했다.

if graph[x][y] == 0: # 이미 방문했던 위치
  continue

• 덱에 값을 새로 넣은 후에 방문 표시를 하는 보통의 경우와 달리 덱의 값을 꺼내는 즉시 바로 방문 표시를 하였다.

x, y = q.popleft()
graph[x][y] = 0

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

코드

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

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
d = [(0, 1), (1, 0)]

def bfs(x, y):
  q = deque([(x, y)])

  while q:
    x, y = q.popleft()

    if graph[x][y] == 0:
      continue

    save = graph[x][y]
    graph[x][y] = 0 

    for i in range(2):
      dx = x + d[i][0] * save
      dy = y + d[i][1] * save

      if 0 <= dx < n and 0 <= dy < n:
        if graph[dx][dy] == -1:
          return True
        q.append([dx, dy])

  return False

print('HaruHaru' if bfs(0, 0) else 'Hing')

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS