Level 3 블록 이동하기 <2020 KAKAO BLIND RECRUITMENT> Python 3

https://programmers.co.kr/learn/courses/30/lessons/60063?language=python3 

코딩테스트 연습 - 블록 이동하기

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_블록이동하기.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from collections import deque

def bfs(R, C):
    global brd, rotate
    # (r1, c1), (r2, c2), d
    # d = 0 -> 가로, d = 1 -> 세로
    visit = [[[[[0] * len(brd[0]) for _ in range(len(brd))] for _ in range(len(brd[0]))] for _ in
               range(len(brd))] for _ in range(2)]
    dr = [-1, 0, 1, 0]
    dc = [0, -1, 0, 1]
    robot = [[0, 0], [0, 1], 0]
    visit[robot[2]][robot[0][0]][robot[0][1]][robot[1][0]][robot[1][1]] = 1
    q = deque([[robot, 0]])

    while q:
        rb, sec = q.popleft()
        if (rb[0][0] == R and rb[0][1] == C) or (rb[1][0] == R and rb[1][1] == C):
            return sec

        #90도 회전
        for l in range(2):
            for i in range(2):
                r = rb[(l+1)%2][0]
                c = rb[(l+1)%2][1]
                nr1 = rb[l][0] + rotate[rb[2]][l][i][0][0]
                nc1 = rb[l][1] + rotate[rb[2]][l][i][0][1]
                nr2 = rb[l][0] + rotate[rb[2]][l][i][1][0]
                nc2 = rb[l][1] + rotate[rb[2]][l][i][1][1]
                if not (0 <= nr1 <= R and 0 <= nr2 <= R and 0 <= nc1 <= C and 0 <= nc2 <= C): continue
                if brd[nr1][nc1] or brd[nr2][nc2]: continue
                if rb[2] == 0:
                    if r < nr2:
                        r1, c1, r2, c2 = r, c, nr2, nc2
                    else:
                        r1, c1, r2, c2 = nr2, nc2, r, c
                    if visit[1][r1][c1][r2][c2]: continue
                    visit[1][r1][c1][r2][c2] = 1
                    q.append([[[r1, c1], [r2, c2], 1], sec+1])

                else:
                    if c < nc2:
                        r1, c1, r2, c2 = r, c, nr2, nc2
                    else:
                        r1, c1, r2, c2 = nr2, nc2, r, c
                    if visit[0][r1][c1][r2][c2]: continue
                    visit[0][r1][c1][r2][c2] = 1
                    q.append([[[r1, c1], [r2, c2], 0], sec+1])

        #한 칸 이동
        for ddr, ddc in zip(dr, dc):
            r1 = rb[0][0] + ddr
            c1 = rb[0][1] + ddc
            r2 = rb[1][0] + ddr
            c2 = rb[1][1] + ddc
            if not (0 <= r1 <= R and 0 <= r2 <= R and 0 <= c1 <= C and 0 <= c2 <= C): continue
            if brd[r1][c1] or brd[r2][c2]: continue
            if visit[rb[2]][r1][c1][r2][c2]: continue
            visit[rb[2]][r1][c1][r2][c2] = 1
            q.append([[[r1, c1], [r2, c2], rb[2]], sec+1])

def solution(board):
    global brd, rotate
    brd = board
    rotate = [
        #d = 0일 때,
        [[[[1, 0], [1, 1]], [[-1, 0], [-1, 1]]], [[[1, 0], [1, -1]], [[-1, 0], [-1, -1]]]],
        #d = 1일 때,
        [[[[0, 1], [1, 1]], [[0, -1], [1, -1]]], [[[0, 1], [-1, 1]], [[0, -1], [-1, -1]]]]
    ]

    return  bfs(len(board)-1, len(board[0])-1)

---

풀이 과정

풀이 시간 1시간 11분

from collections import deque

def bfs(R, C):
    global brd, rotate
    
	#visit[로봇의 방향][r1][c1][r2][c2] = 방문 여부
    visit = [[[[[0] * len(brd[0]) for _ in range(len(brd))] for _ in range(len(brd[0]))] for _ in
               range(len(brd))] for _ in range(2)]
               
    #상, 좌, 하, 우
    dr = [-1, 0, 1, 0]
    dc = [0, -1, 0, 1]
    
    #로봇 상태 초기화
    # (r1, c1), (r2, c2), d
    # d = 0 -> 가로, d = 1 -> 세로
    robot = [[0, 0], [0, 1], 0]
    
    #맨 처음 로봇 방향과 위치 방문처리
    visit[robot[2]][robot[0][0]][robot[0][1]][robot[1][0]][robot[1][1]] = 1
    
    #[로봇 상태, 현재 초]
    q = deque([[robot, 0]])

    while q:
        rb, sec = q.popleft()
        
        #도착지에 도착한 경우, 현재 초 return
        if (rb[0][0] == R and rb[0][1] == C) or (rb[1][0] == R and rb[1][1] == C):
            return sec

        #90도 회전하기
        #l = 회전 기준 위치, i = 회전 방향
        for l in range(2):
            for i in range(2):
            	#회전이 일어나지 않는 다른 로봇의 위치 (r, c)
                r = rb[(l+1)%2][0]
                c = rb[(l+1)%2][1]
                
                #회전 가능 여부 체크
                #(nr1, nr2) -> 벽이 있는지 체크해야 할 위치
                nr1 = rb[l][0] + rotate[rb[2]][l][i][0][0]
                nc1 = rb[l][1] + rotate[rb[2]][l][i][0][1]
                
                #(nr2, nr2) -> 회전 후 위치(역시 벽이 있는지 체크해야 한다)
                nr2 = rb[l][0] + rotate[rb[2]][l][i][1][0]
                nc2 = rb[l][1] + rotate[rb[2]][l][i][1][1]
                
                #체크해야 할 두 위치 중 하나라도 범위를 벗어난 경우, 무시한다
                if not (0 <= nr1 <= R and 0 <= nr2 <= R and 0 <= nc1 <= C and 0 <= nc2 <= C): continue
                #체크해야 할 두 위치 중 하나라도 벽인 경우, 무시한다
                if brd[nr1][nc1] or brd[nr2][nc2]: continue
                
                #로봇이 가로 방향인 경우,
                if rb[2] == 0:
                	#회전 이후 로봇 위치 설정
                    if r < nr2:
                        r1, c1, r2, c2 = r, c, nr2, nc2
                    else:
                        r1, c1, r2, c2 = nr2, nc2, r, c
                    
                    #이전에 탐색했던 조건인 경우, 무시한다
                    if visit[1][r1][c1][r2][c2]: continue
                    
                    #현재 조건 방문 처리
                    visit[1][r1][c1][r2][c2] = 1
                    #회전 후 세로 방향으로 로봇 방향이 변경된다
                    q.append([[[r1, c1], [r2, c2], 1], sec+1])
				
                #로봇이 세로 방향인 경우,
                else:
                	#회전 이후 로봇 위치 설정
                    if c < nc2:
                        r1, c1, r2, c2 = r, c, nr2, nc2
                    else:
                        r1, c1, r2, c2 = nr2, nc2, r, c
                        
                    #이전에 탐색했던 조건인 경우, 무시한다    
                    if visit[0][r1][c1][r2][c2]: continue
                    
                    #현재 조건 방문 처리
                    visit[0][r1][c1][r2][c2] = 1
                    #회전 후 가로 방향으로 로봇 방향이 변경된다
                    q.append([[[r1, c1], [r2, c2], 0], sec+1])

        #한 칸 이동하기
        for ddr, ddc in zip(dr, dc):
            r1 = rb[0][0] + ddr
            c1 = rb[0][1] + ddc
            r2 = rb[1][0] + ddr
            c2 = rb[1][1] + ddc
            
            #이동한 두 위치 중 하나라도 범위를 벗어난 경우, 무시한다
            if not (0 <= r1 <= R and 0 <= r2 <= R and 0 <= c1 <= C and 0 <= c2 <= C): continue
            #이동한 두 위치 중 하나라도 벽인 경우, 무시한다
            if brd[r1][c1] or brd[r2][c2]: continue
            #이동한 두 위치의 조합을 이전에 탐색한 경우, 무시한다
            if visit[rb[2]][r1][c1][r2][c2]: continue
            
            #현재 조건 방문처리
            visit[rb[2]][r1][c1][r2][c2] = 1
            #로봇 방향은 그대로 유지된다
            q.append([[[r1, c1], [r2, c2], rb[2]], sec+1])

def solution(board):
    global brd, rotate
    brd = board
    
    #rotate[로봇 방향][회전 기준 위치][0] = 90도 회전시 벽이 있는지 체크해야 할 곳
    #rotate[로봇 방향][회전 기준 위치][1] = 90도 회전시 벽이 있는지 체크한 후, 회전한 위치
    rotate = [
        #d = 0일 때,
        [[[[1, 0], [1, 1]], [[-1, 0], [-1, 1]]], [[[1, 0], [1, -1]], [[-1, 0], [-1, -1]]]],
        #d = 1일 때,
        [[[[0, 1], [1, 1]], [[0, -1], [1, -1]]], [[[0, 1], [-1, 1]], [[0, -1], [-1, -1]]]]
    ]

    return  bfs(len(board)-1, len(board[0])-1)