[프로그래머스] 블록 이동하기 - python

반응형

블록 이동하기

문제

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.

로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.

"0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

제한사항

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

풀이

BFS로 풀면서 시간을 갱신했다. 회전을 구현하면서 방향을 생각하면서 풀다 보니까 너무 복잡해져서 다른 사람 풀이를 참고했다.

 

맵 변형하기

초기에 주어진 맵을 늘려서 외곽에 벽을 놓으면 로봇이 맵을 벗어나지 않는지 더 쉽게 판정할 수 있다.

new_board = [[1] * (n + 2) for _ in range(n + 2)]
    for i in range(n):
        for j in range(n):
            new_board[i + 1][j + 1] = board[i][j]

위치 정보 저장

각 위치 정보를 튜플로 만들어서 집합 자료형으로 관리할 경우 {(1, 1), (1, 2)}와 {(1, 2), (1, 1)}은 같은 객체로 취급되기 때문에 한번 방문한 (큐에 들어간) 로봇의 위치는 다시 방문하지 않는다.

집합 자료형을 사용하지 않고 매번 정렬해서 넣는 방법도 있지만 집합 자료형을 사용하는 게 더 빠르고 간편하다.

방문 길이 문제에서 중복을 제거하는 방식과 같다.

중복을 제거하지 않으면 시간 초과가 난다.

이동

내가 잘못 이해한 부분은 로봇이 한 방향으로만 갈 수 있다고 생각한 것이다.

만약에 가로로 놓여 있으면 왼쪽 아니면 오른쪽으로만 이동할 수 있는 줄 알았다. 그래서 한쪽 방향으로 이동하다가 회전이 필요할 때만 회전을 하려고 하다보니 조건이 너무 복잡해졌다.

 

근데 그게 아니라 놓인 방향만 유지한 채로 상, 하, 좌, 우 다 움직일 수 있다.

현재 위치에서 상, 하, 좌, 우로 갈 수 있는 모든 위치를 탐색해서 넣은 후 회전 가능한 위치도 모두 넣어서 탐색할 수 있도록 해야 한다.

  for dx, dy in dirs:
        next_fx, next_fy = fx + dx, fy + dy
        next_bx, next_by = bx + dx, by + dy
        if board[next_fx][next_fy] == 0 and board[next_bx][next_by] == 0:
            next_pos.append({(next_fx, next_fy), (next_bx, next_by)})

회전

회전은 4가지 케이스를 고려해야한다.

각 회전을 할 때마다 회전 축을 다르게 할 수 있기 때문에 각각 경우의 2개씩 총 8개의 회전 결과가 나오게 된다 (모두 가능할 경우)

나는 이전 위치를 유지한 채로 옮기려고 해서 복잡했는데 그냥 버리고 회전축을 기준으로 새로 위치를 계산해서 넣어주면 된다.

가로로 놓여 있을 때

• 아래쪽으로 회전하는 경우: 아래 두 칸에 벽이 없어야 한다.
• 위쪽으로 회전하는 경우 : 위 두 칸에 벽이 없어야 한다.

if fx == bx:
        for i in [-1, 1]:
            if board[fx + i][fy] == 0 and board[bx + i][by] == 0:
                next_pos.append({(fx, fy), (fx + i, fy)})
                next_pos.append({(bx, by), (bx + i, by)})

세로로 놓여 있을 때

• 오른쪽으로 회전하는 경우: 오른쪽 두 칸에 벽이 없어야 한다.
• 왼쪽으로 회전하는 경우: 왼쪽 두 칸에 벽이 없어야 한다.

elif fy == by:
        for i in [-1, 1]:
            if board[fx][fy + i] == 0 and board[bx][by + i] == 0:
                next_pos.append({(fx, fy), (fx, fy + i)})
                next_pos.append({(bx, by), (bx, by + i)})

전체 코드

from collections import deque

def get_next_pos(pos, board):
    next_pos = []
    pos = list(pos)
    fx, fy = pos[0]
    bx, by = pos[1]
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for dx, dy in dirs:
        nfx, nfy = fx + dx, fy + dy
        nbx, nby = bx + dx, by + dy
        if board[nfx][nfy] == board[nbx][nby] == 0:
            next_pos.append({(nfx, nfy), (nbx, nby)})
    
    if fx == bx:
        for i in [1, -1]:
            if board[fx + i][fy] == board[bx + i][by] == 0:
                next_pos.append({(fx, fy), (fx + i, fy)})
                next_pos.append({(bx, by), (bx + i, by)})
    elif fy == by:
        for i in [1, -1]:
            if board[fx][fy + i] == board[bx][by + i] == 0:
                next_pos.append({(fx, fy), (fx, fy + i)})
                next_pos.append({(bx, by), (bx, by + i)})
    
    return next_pos
        
                
                
def solution(board):
    answer = 0
    n = len(board)
    new_board = [[1] * (n + 2) for _ in range(n + 2)]
    for i in range(n):
        for j in range(n):
            new_board[i + 1][j + 1] = board[i][j]
    
    q = deque([({(1, 1), (1, 2)}, 0)])
    visited = []
    
    while q:
        pos, cost = q.popleft()
        if (n, n) in pos:
            return cost
        for next_pos in get_next_pos(pos, new_board):
            if next_pos not in visited:
                visited.append(next_pos)
                q.append((next_pos, cost + 1))
    return answer