[Python] 2020 KAKAO BLIND RECRUITMENT - 블록 이동하기

https://school.programmers.co.kr/learn/courses/30/lessons/60063

프로그래머스

 

이번 문제는 2020 카카오 공채 1차 코딩테스트 7번 문제로 출제된 블록 이동하기 문제이다. 

 

이렇게 맵을 탐색하는 문제는 굉장히 흔한데, 그런 문제들과 이 문제의 가장 큰 차이점은 바로 로봇이 한 칸이 아닌 두 칸을 차지한다는 점이다. 또한 로봇이 이동할 때에도 두 칸이 모두 이동할 수 있어야 한다는 제약이 걸려있다. 또 이러한 점을 고려하여 로봇이 회전까지 할 수 있다... 

 

위의 조건들을 고려해 보았을 때, 특정 위치에서 로봇이 할 수 있는 행동은 총 여덟 가지가 나온다. 

 

1. 왼쪽 축을 기준으로 시계 방향 회전

2. 왼쪽 축을 기준으로 반시계 방향 회전

3. 오른쪽 축을 기준으로 시계 방향 회전

4. 오른쪽 축을 기준으로 반시계 방향 회전

5, 6, 7, 8. 상하좌우 이동

 

위의 조건을 따라 그대로 구현하기만 하면 된다! 

 

하지만 이대로 구현만 하면 같은 상황이 반복될 수 있으므로, 같은 상황에서는 검사를 하지 않도록 조치를 취해야 한다. 나는 dp 테이블을 딕셔너리 형태로 만들어 관리했다. 들어가는 값은 (y1, x1, y2, x2, direction)을 넣었고, 만약 같은 값이 dp 테이블에 이미 존재한다면 검사를 하지 않고 넘어가는 방식으로 구현했다. 이때 같은 상황에서 (y1, x1), (y2, x2)의 좌표만 반전되는 경우를 피하기 위해서 x1이 항상 x2보다 작게 오게끔 하였고, 만약 x1이 x2와 같은 상황에서는 y1이 y2보다 작게끔 해주었다. 

 

코드는 아래와 같다! 

 

from collections import deque

def check_turn(y1, x1, y2, x2, board, direction):
    if direction == 0:
        if board[y1-1][x1] == 0 and board[y2-1][x2] == 0:
            return True
        else:
            return False
    elif direction == 1:
        if board[y1+1][x1] == 0 and board[y2+1][x2] == 0:
            return True
        else:
            return False
    elif direction == 2:
        if board[y1][x1-1] == 0 and board[y2][x2-1] == 0:
            return True
        else:
            return False
    elif direction == 3:
        if board[y1][x1+1] == 0 and board[y2][x2+1] == 0:
            return True
        else:
            return False
        
def solution(board):
    answer = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    robot = [[0, 0], [0, 1], 0, 0]
    q = deque()
    q.append(robot)
    stop = 0
    dp = {}
    while q:
        tmp = q.popleft()
        if tmp[0][0] == len(board) - 1 and tmp[0][1] == len(board) - 1:
            answer = tmp[3]
            break
        if tmp[1][0] == len(board) - 1 and tmp[1][1] == len(board) - 1:
            answer = tmp[3]
            break
        if (tmp[0][0], tmp[0][1], tmp[1][0], tmp[1][1], tmp[2]) in dp:
            continue
        dp[(tmp[0][0], tmp[0][1], tmp[1][0], tmp[1][1], tmp[2])] = True
        
        y1, x1 = tmp[0]
        y2, x2 = tmp[1]
        direction = tmp[2]
        time = tmp[3]
        if direction == 0:
            if y1 > 0 and check_turn(y1, x1, y2, x2, board, 0):
                q.append(([y2-1, x1], [y1, x1], 1, time+1))
                q.append(([y2-1, x2], [y2, x2], 1, time+1))
            if y1 < len(board) - 1 and check_turn(y1, x1, y2, x2, board, 1):
                q.append(([y1, x1], [y2+1, x1], 1, time+1))
                q.append(([y2, x2], [y2+1, x2], 1, time+1))
        elif direction == 1:
            if x1 > 0 and check_turn(y1, x1, y2, x2, board, 2):
                q.append(([y1, x1-1], [y1, x1], 0, time+1))
                q.append(([y2, x2-1], [y2, x2], 0, time+1))
            if x1 < len(board) - 1 and check_turn(y1, x1, y2, x2, board, 3):
                q.append(([y1, x1], [y1, x1+1], 0, time+1))
                q.append(([y2, x2], [y2, x2+1], 0, time+1))
                    
        for i in range(4):
            nx1 = tmp[0][1] + dx[i]
            ny1 = tmp[0][0] + dy[i]
            nx2 = tmp[1][1] + dx[i]
            ny2 = tmp[1][0] + dy[i]
            if 0 <= nx1 < len(board) and 0 <= ny1 < len(board) and 0 <= nx2 < len(board) and 0 <= ny2 < len(board):
                robot = ([ny1, nx1], [ny2, nx2], tmp[2], tmp[3]+1)
                answer = robot[3]
                if board[ny1][nx1] == 0 and board[ny2][nx2] == 0:
                    q.append(robot)
                    
        if stop == 1:
            break
    return answer