[BOJ] 1600 : 말이 되고픈 원숭이

오다혜·2021년 11월 11일
0

간단한 bfs 문제라고 생각했는데, 복병이 숨어 있었다.

💡 처음 푼 방법

from collections import deque

K = int(input())
h_dx = [1, 2, -1, -2, 1, 2, -1, -2]
h_dy = [2, 1, -2, -1, -2, -1, 2, 1]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 0, 0에서 시작
q = deque([(0, 0, 0, 0)])

# (H-1, W-1) 까지 가야 함
W, H = map(int, input().split())

# 체스판 만들기
visited = [[0 for _ in range(W)] for _ in range(H)]
visited[0][0] = 1
board = []
for i in range(H):
    board.append(list(map(int, input().split())))


def move_monkey():
    while len(q):
        cx, cy, move, h_move = q.popleft()

        # 한 번 움직이기
        move += 1

        # 아직 말처럼 K번 안 움직였으면 말처럼 원숭이 움직이기
        if h_move < K:
            for i in range(8):
                nx, ny = cx + h_dx[i], cy + h_dy[i]
                if 0 <= nx < H and 0 <= ny < W and visited[nx][ny] == 0 and board[nx][ny] != 1:
                    if nx == H - 1 and ny == W - 1:
                        return move
                    q.append((nx, ny, move, h_move + 1))
                    visited[cx][cy] = 1

        # 원숭이 기본 움직이기
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx < H and 0 <= ny < W and visited[nx][ny] == 0 and board[nx][ny] != 1:
                if nx == H - 1 and ny == W - 1:
                    return move
                q.append((nx, ny, move, h_move))
                visited[cx][cy] = 1
    return -1


print(move_monkey())
  • 함수 move_monkey() 가 bfs함수
  • 상하좌우 움직임과 말처럼 움직이는 것은 각각 dx, dy와 h_dx, h_dy 로 만들어서 for 문으로 움직이도록
  • visited 는 1차원 list로 만들어서 방문 처리

계속 시간초과가 나서, 만약 이동했을 때 조건에 맞아서 큐에 들어가야 하는 위치이면 이동 시키기 전에 바로 visited 처리를 해줬다.

근데, 이렇게 처리를 해줬는데도 시간초과가 났다..😢

💡 변경한 코드

from collections import deque

K = int(input())
h_dx = [1, 2, -1, -2, 1, 2, -1, -2]
h_dy = [2, 1, -2, -1, -2, -1, 2, 1]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 0, 0에서 시작
q = deque([(0, 0, 0, 0)])

# (H-1, W-1) 까지 가야 함
W, H = map(int, input().split())

# 체스판 만들기
board = []
for i in range(H):
    board.append(list(map(int, input().split())))

# 방문 처리
visited = [[[0 for _ in range(K + 1)] for _ in range(W)] for _ in range(H)]
visited[0][0][0] = 1


def check(nx, ny, h_move):
    if 0 <= nx < H and 0 <= ny < W:
        if visited[nx][ny][h_move] == 0 and board[nx][ny] != 1:
            return True
    return False


def move_monkey():
    while len(q):
        cx, cy, move, h_move = q.popleft()

        if cx == H - 1 and cy == W - 1:
            return move

        # 한 번 움직이기
        move += 1

        # 아직 말처럼 K번 안 움직였으면 말처럼 원숭이 움직이기
        if h_move < K:
            for i in range(8):
                nx, ny = cx + h_dx[i], cy + h_dy[i]
                if check(nx, ny, h_move + 1):
                    q.append((nx, ny, move, h_move + 1))
                    visited[nx][ny][h_move + 1] = 1

        # 원숭이 기본 움직이기
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if check(nx, ny, h_move):
                q.append((nx, ny, move, h_move))
                visited[nx][ny][h_move] = 1

    return -1


print(move_monkey())

⭐️ 핵심

말의 움직임으로 이동을 했는지, 아닌지를 파악하기 위해서 visited를 3차원으로 만드는 것이 핵심이다.

visited = [[[[0 for _ in range(K + 1)] for _ in range(W)] for _ in range(H)]]
visited[0][0][0] = 1

왜 visited를 3차원으로 만들어야 하는지 처음엔 이해가 잘 안 갔다. 기존 코드의 경우에도 전체 움직인 수(move)와 말의 움직임(h_move)을 나타낸 수를 큐에 넣어서 기억하고 있었기 때문에 굳이 말의 움직임까지 3차원으로 만들면 방문처리하는 데에 시간이 더 많이 걸린다고 생각이 들었기 때문이다.

그렇다면..

어떤 좌표에 한 번 방문했다면 말처럼 왔는지, 원숭이처럼 왔는지가 차이가 있을까?

정답은, "그렇다" 다.

어떤 x 좌표를 도착한 상황일 경우, 크게 두 가지로 나누어보자.

  1. 아직 말의 움직임으로 이동할 수 있음
  2. 말의 움직임을 다 써서 상하좌우로만 이동할 수 있음

만약, 이 경우에 x 좌표 이후에 장애물이 있다면? 2번 case에선 더이상 움직이지 못 할 것이다. 그치만 1번 case라면 말의 움직임을 사용해서 장애물을 뛰어넘을 수 있다. visited를 1차원 배열로 만들게 되면(처음 내가 풀이한 방법), 위와 같은 상황에서 말의 움직임을 써서 해당 위치에 도달한 경우가 더 빨랐을 때엔 visited가 이미 1이기 때문에 1번 case가 있음에도 불구하고 고려하지 못하게 된다.

profile
프론트엔드에 백엔드 한 스푼 🥄

0개의 댓글