[1day 1sol] 점프왕 쩰리 (Small)

문제

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

16173번: 점프왕 쩰리 (Small)

구현

• 시작점: 왼쪽 맨위, 종료점: 오른쪽 맨 아래
• 구간: N x N matrix (2 <= N <= 3)
• 규칙
  1. 구간 외에 나가면 패배
  2. 쪨리의 이동방향 오른쪽 or 아래
  3. 종료점에 도착하면 승리
  4. 한번에 이동가능한 칸수는 현재 밟고있는 수
• 게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.
• 결과: 도달가능(HaruHaru), 도달 불가능(Hing)

코드 (메모리초과)

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


def BFS(matrix):
    l = len(matrix)
    q = deque()
    q.append((0, 0))
    # 오른쪽 or 아래
    d = [(1, 0), (0, 1)]
    while q:
        x, y = q.popleft()
        val = matrix[x][y]

        # 종료지점에 도착했을 떄
        if x == l - 1 and y == l - 1:
            return "HaruHaru"

        for i in range(len(d)):
            dx = x + d[i][0] * val
            dy = y + d[i][1] * val
            if (0 <= dx < l) and (0 <= dy < l):
                q.append((dx, dy))
    return "Hing"


# make matrix (N x N)
n = int(input())
board = list(list(map(int, input().split())) for _ in range(n))
print(BFS(board))

 

코드 (해결)

 

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


def BFS(matrix, visit, l):
    q = deque()
    q.append((0, 0))
    # 오른쪽 or 아래
    d = [(1, 0), (0, 1)]
    while q:
        x, y = q.popleft()
        val = matrix[x][y]

        # 종료지점에 도착했을 떄
        if matrix[x][y] == -1:
            return "HaruHaru"

        for i in range(len(d)):
            dx = x + d[i][0] * val
            dy = y + d[i][1] * val
            if (0 <= dx < l) and (0 <= dy < l):
                # 방문 했더라면 다음 인덱스로 넘어간다.(이로인해서 메모리를 덜 사용)
                if visit[dx][dy]:
                    continue
                # 방문하지 않았다면 방문으로 변경한다.
                else:
                    visit[dx][dy] = True
                    q.append((dx, dy))
    return "Hing"


# make board matrix (N x N) & visited matrix
n = int(input())
board = list(list(map(int, input().split())) for _ in range(n))
visited = list([False] * n for _ in range(n))
print(BFS(board, visited, n))

느낀점

머리속으로는 알고리즘을 구현하는데에 문제는 없었지만, 메모리 초과라는 문제에 직면하게되었다. 처음에는 "왜?"라는 질문이 나오게되었지만 알고리즘을 생각해보니 필요없는 for문을 굳이 돌려야하지는 않기때문에 반복을 없애주기위해서 visited라는 이미 값을 확인한 곳은 제외를 해주는 방식으로 코딩을 이어나가보니 메모리 문제점을 해결할 수 있었다.