[Algorithm] programmers/kakao/2020blind/블록 이동하기

문제 설명

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

로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.
로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

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

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

제한사항

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

접근법

>> 흠 자식이 최대 8개인 트리의 탐색으로 생각하였다.
>> level-order traverse 기법, 즉 queue를 사용하였다. bfs라고 봐도 될 듯
>> 첫 시도에서는 robot이라는 class를 만들어서 테스트 해봄
>> 두 번째 시도에서는 굳이 class가 없어도 된다고 생각하여 그냥 비슷하게 짜봄
>> 왜 10번은 아예 틀렸다고 나오고, 9,13,14는 시간초과냐 ㅜㅜ

코드1

## 테스트9,10,13,14 실패(시간초과)

import sys
sys.setrecursionlimit(10**6)
import math
class pos:
    def __init__(self, r, c):
        self.r=r
        self.c=c

class robot:
    def __init__(self, map):
        self.p1 = pos(0, 0)
        self.p2 = pos(0, 1)
        self.map = map[:]
        self.size = len(map)
        self.dp = [[self.size*self.size+1000 for e in row] for row in map]

        self.dp[0][0] =0
        self.dp[0][1] =0


    def check(self):

        lim = self.size
        r = self.p1.r
        c = self.p1.c
        ## p1이 map 밖에 있어요
        if r < 0 or r >= lim or c < 0 or c >=lim:
            return False

        ## p1이 벽에 있어요
        if self.map[r][c] ==1 :
            return False

        r = self.p2.r
        c = self.p2.c
        ## p2이 map 밖에 있어요
        if r < 0 or r >= lim or c < 0 or c >=lim:
            return False

        ## p2이 벽에 있어요
        if self.map[r][c] ==1 :
            return False

        return True

    def condition(self, count):

        determine = 0
        if count <= self.dp[self.p1.r][self.p1.c]:
            determine+=1
        if count <= self.dp[self.p2.r][self.p2.c]:
            determine+=1
        if determine > 0:
            self.dp[self.p1.r][self.p1.c] = min(count, self.dp[self.p1.r][self.p1.c])
            self.dp[self.p2.r][self.p2.c] = min(count, self.dp[self.p2.r][self.p2.c])
            return True
        else:
            return False

    def left(self):
        self.p1.c -=1
        self.p2.c -=1
        if self.check():
            return True
        else :
            self.right()
            return False

    def right(self):
        self.p1.c +=1
        self.p2.c +=1
        if self.check():
            return True
        else:
            self.left()
            return False

    def up(self):
        self.p1.r -=1
        self.p2.r -=1
        if self.check():
            return True
        else:
            self.down()
            return False

    def down(self):
        self.p1.r +=1
        self.p2.r +=1
        if self.check():
            return True
        else :
            self.up()
            return False

    def rot(self, p1 = 1, ccw=1): ## p1 (1 or -1), ccw (1 or -1)
        delr = p1*self.p2.r - p1*self.p1.r
        delc = p1*self.p2.c - p1*self.p1.c
        normr = int(math.cos(math.pi/2*ccw)*delr - math.sin(math.pi/2*ccw)*delc)
        normc = int(math.sin(math.pi/2*ccw)*delr + math.cos(math.pi/2*ccw)*delc)
        if p1 == 1: ## axis = p1
            ##
            checkr = delr+normr + self.p1.r
            checkc = delc+normc + self.p1.c
            dstr = normr +self.p1.r
            dstc = normc +self.p1.c

            if checkr < 0 or checkr >= self.size or checkc < 0 or checkc >= self.size:
                return False

            if dstr < 0 or dstr>=self.size or dstc < 0 or dstc >= self.size:
                return False

            if self.map[checkr][checkc]==1 or self.map[dstr][dstc]==1:
                return False
            else :
                self.p2.r = dstr
                self.p2.c = dstc
                return True
        else:
            ##
            checkr = delr+normr + self.p2.r
            checkc = delc+normc + self.p2.c
            dstr = normr +self.p2.r
            dstc = normc +self.p2.c

            if checkr < 0 or checkr >= self.size or checkc < 0 or checkc >= self.size:
                return False

            if dstr < 0 or dstr>=self.size or dstc < 0 or dstc >= self.size:
                return False

            if self.map[checkr][checkc] or self.map[dstr][dstc]:
                return False
            else :
                self.p1.r = dstr
                self.p1.c = dstc
                return True

    def reset(self, p1, p2):
        self.p1.r = p1.r
        self.p1.c = p1.c
        self.p2.r = p2.r
        self.p2.c = p2.c

    def action(self, count):
        queue=[]
        memo_p1 = pos(self.p1.r, self.p1.c)
        memo_p2 = pos(self.p2.r, self.p2.c)
        queue.append([memo_p1.r, memo_p1.c, memo_p2.r, memo_p2.c, count])

        while len(queue):
            pp1r, pp1c, pp2r, pp2c, pcount = queue.pop(0)
            if pp1r == self.size-1 and pp1c == self.size-1:
                break
            if pp1r == self.size-1 and pp2c == self.size-1:
                break

            self.reset(pos(pp1r,pp1c), pos(pp2r,pp2c))
            if self.left():
                if self.condition(pcount+1):
                    queue.append([self.p1.r,self.p1.c, self.p2.r, self.p2.c, pcount+1])
            else:
                self.right()

            self.reset(pos(pp1r,pp1c), pos(pp2r,pp2c))
            if self.right():
                if self.condition(pcount+1):
                    queue.append([self.p1.r,self.p1.c, self.p2.r, self.p2.c, pcount+1])
            else:
                self.left()

            self.reset(pos(pp1r,pp1c), pos(pp2r,pp2c))
            if self.up():
                if self.condition(pcount+1):
                    queue.append([self.p1.r,self.p1.c, self.p2.r, self.p2.c, pcount+1])
            else:
                self.down()

            self.reset(pos(pp1r,pp1c), pos(pp2r,pp2c))
            if self.down():
                if self.condition(pcount+1):
                    queue.append([self.p1.r,self.p1.c, self.p2.r, self.p2.c, pcount+1])
            else:
                self.up()    

            for axis in [1,-1]:
                for ccw in [1,-1]:
                    self.reset(pos(pp1r,pp1c), pos(pp2r,pp2c))
                    if self.rot(p1=axis, ccw=ccw):
                        if self.condition(pcount+1):
                            queue.append([self.p1.r,self.p1.c, self.p2.r, self.p2.c, pcount+1])
                        else: 
                            self.rot(p1=axis, ccw=ccw*(-1))

def solution(board):
    quanx = robot(board)
    quanx.action(0)  
    n = len(board)
    return quanx.dp[n-1][n-1]

board = [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]]
result = solution(board)
print(result)

코드2

import math

def solution(board):

    lim = len(board)
    infinite = lim*lim+1
    board = [[infinite if e == 0 else -1 for e in row] for row in board]
    board[0][0] = 0
    board[0][1] = 0

    right,down,left,up=[0,1,2,3]
    p = [0, 0, 0, 1]    
    queue = []

    def renewal(pos, distance):
        # 움직인 후의 좌표
        r1,c1,r2,c2=pos

        if distance <= board[r1][c1] or distance <=board[r2][c2]:
            board[r1][c1] = min(board[r1][c1],distance)
            board[r2][c2] = min(board[r2][c2],distance)
            return  True

        return False


    def check_trans(pos):
        r1,c1,r2,c2 = pos
        #boundary condtion
        if c1 <0 or c1>=lim or c2<0 or c2>=lim or r1<0 or r1>=lim or r2<0 or r2>=lim:
            return False
        # wall condtion
        if board[r1][c1] < 0 or board[r2][c2] < 0:
            return False
        # distance condtion
        # 아니야 일단 가고, 갱신만 잘해주면 됩니다.
        return True

    # trans  할 수 있으면 True와 움직인 후의 좌표를 반환한다. 
    def move_trans(pos, distance, move): 
        # 움직이기 전의 좌표
        r1,c1,r2,c2 = pos
        if move == left:
            c1-=1
            c2-=1
        elif move == right:
            c1+=1
            c2+=1
        elif move == up:
            r1-=1
            r2-=1
        elif move ==down:
            r1+=1
            r2+=1
        if check_trans([r1,c1,r2,c2]):
            if renewal([r1,c1,r2,c2], distance+1):
                queue.append([[r1,c1,r2,c2], distance+1])


    # rotate 할 수 있으면 True와 움직인 후의 좌표를 반환한다.
    def move_rotate(pos, distance, axis=1, ccw=1):
        r1,c1,r2,c2 = pos

        delr = axis*(r2 - r1)
        delc = axis*(c2 - c1)
        normr = int(math.cos(math.pi/2*ccw)*delr - math.sin(math.pi/2*ccw)*delc)
        normc = int(math.sin(math.pi/2*ccw)*delr + math.cos(math.pi/2*ccw)*delc)

        if axis == 1: ## axis = number1
            checkr = delr+normr + r1
            checkc = delc+normc + c1
            dstr = normr +r1
            dstc = normc +c1

            ## boundary condtion
            if checkr < 0 or checkr >= lim or checkc < 0 or checkc >= lim:
                return

            ## boundary condtion
            if dstr < 0 or dstr>=lim or dstc < 0 or dstc >= lim:
                return

            ## wall condtion
            if board[checkr][checkc]<0 or board[dstr][dstc]<0:
                return
            else :
                if renewal([r1, c1, dstr, dstc], distance+1):
                    queue.append([[r1, c1, dstr, dstc], distance+1])
        else:
            ##
            checkr = delr+normr + r2
            checkc = delc+normc + c2
            dstr = normr + r2
            dstc = normc + c2

            if checkr < 0 or checkr >= lim or checkc < 0 or checkc >= lim:
                return

            if dstr < 0 or dstr>=lim or dstc < 0 or dstc >= lim:
                return

            if board[checkr][checkc]<0 or board[dstr][dstc] <0:
                return
            else :
                if renewal([dstr, dstc, r2, c2], distance+1):
                    queue.append([[dstr, dstc, r2, c2], distance+1])


    distance = 0
    queue.append([p, distance])

    while len(queue):

        # print(board)
        # print(len(queue))
        pos, distance = queue.pop(0)
        # print(pos)

        if board[lim-1][lim-1] < infinite:
            return board[lim-1][lim-1]

        for dir in [right,down, left,up]:
            move_trans(pos, distance, dir)

        for axis in [1,-1]:
            for ccw in [1,-1]:
                move_rotate(pos, distance, axis=axis, ccw=ccw)


    return board[lim-1][lim-1]