[이것이 코딩 테스트다 with Python] Chapter 13. DFS/BFS - 블록 이동하기

 

< 블록 이동하기 >

 

💬 문제 설명

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다.
....

 

입력 ( board )	출력 ( result )
[ [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] ]	7

💬 입력 조건

• board의 한 변의 길이 N ( 5 ≤ N ≤ 100 ) 
• board의 원소는 0 , 1 ( 0 : 길,  1 : 벽)
• 로봇이 처음에 놓여 있는 위치  ( 1, 1 ), ( 1, 2 ) 항상 0
• 로봇이 항상 목적지에 도달할 수 있는 경우만 주어짐 

💬 출력 조건

• 로봇이 ( N, N ) 지점에 도착하는 최단시간 

---

✍ 문제요약

board라는 2차원 배열이 주어진다. 0, 1 ( 0 : 길,  1 : 벽) 로만 이루어져있고, N x N 크기를 가진다. 또한 2 x 1 크기의 로봇이 주어지고, 이 로봇은 항상 ( 1, 1 ), ( 1, 2 ) 에 가로로 위치한다. 이 로봇은 1초 동안 이동 or 90도 회전을 한 번 할 수 있다. 이동의 경우 상, 하, 좌, 우 이동이 가능하다. 회전의 경우 고려할 것이 많다. 로봇이 가로일 때 왼쪽을 축으로 위, 아래 회전 + 오른쪽을 축으로 위, 아래 회전이 가능하다. 로봇이 세로일때는 위쪽을 축으로 왼쪽, 오른쪽 회전 + 아래쪽을 축으로 왼쪽, 오른쪽 회전이 가능하다. 회전 시 거쳐가는 길에 벽이 있으면 회전이 불가능하다. 이를 유의하여 ( N, N ) 위치에 로봇이 도착할 수 있는 최단시간을 구하여라.

💯 문제링크

프로그래머스의 "블록 이동하기"와 동일한 문제이다.

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

프로그래머스

---

✅  문제 풀이

고려해야할 것이 많아서 문제 해결하는데 정말 많은 시간을 썼다. BFS와 구현을 합쳐 놓은 문제라고 생각한다. 

⛔ 아이디어

• 로봇이 1초동안 이동하는 위치와 이동 했을 때의 로봇의 상태를 파악해야한다.
  
  
  • 처음 상태에서 1초 뒤 모습을 살펴보자
  • 아래의 상태를 보면 빨간색 으로 표시된 부분들만 이동 or 회전이 가능한 동작이다.

상 ( X )	우  ( O )	하  ( O )	좌  ( X )
왼쪽을 축으로 위 ( X )	왼쪽을 축으로 아래 ( O )	오른쪽을 축으로 위 ( X )	오른쪽을 축으로 아래 ( O )

 

• 1초동안 이동한 로봇의 위치 및 상태를 기억해야한다.
• 방문 표시를 위한 새로운 배열을 만들어서, 1초간 로봇이 이동한 뒤에 방문 표시를 해야한다.

우  ( O )	하  ( O )	왼쪽을 축으로 아래 ( O )	오른쪽을 축으로 아래 ( O )	방문표시 최종
				4개 지점의 위치와 로봇의 상태(가로, 세로)를 기억해야함

✔️ 정리

• 로봇의 좌표와 상태 ( 왼쪽로봇, 오른쪽로봇, 가로 or 세로 )를 배열에 저장한다.
• 1초간 총 8개 (이동 or 회전 )의 움직임 중 가능한 움직임을 BFS로 확인한다.
• BFS함수가 1회 동작이 곳 1초를 의미한다
  
  • 동작하는 동안 움직임이 가능한 로봇의 좌표와 상태  ( 왼쪽로봇, 오른쪽로봇, 가로 or 세로 ) 를 배열에 저장한다.
  • 동작하는 동안 방문한 지점의 좌표를 배열에 담아둔다.
  • BFS 종료 직전 방문 지점을 표시해준다.
• BFS함수가 1회 동작 후 아직 도착지점에 도달하지 않았으면 위 로봇의 정보가 담긴 새로운 배열로 다시 BFS함수를 실행한다. 

✍️ 코드 뜯어보기 

• board에 상, 하, 좌, 우 에 벽으로 둘러주기

N = len(board) + 2
board = [[1] * N ] + [[1] + lst + [1] for lst in board] + [[1] * N]

 

• 상, 하, 좌, 우 가능한 움직임 확인

for dr1, dc1, dr2, dc2 in ((-1,0,-1,0),(1,0,1,0),(0,-1,0,-1),(0,1,0,1)): # 이동 : 상,하,좌,우
    nr1, nc1, nr2, nc2 = r1 + dr1, c1 + dc1, r2 + dr2, c2 + dc2  # 이동 후 좌표
    if board[nr1][nc1] == 0 and board[nr2][nc2] == 0:            # 이동 했을 시 벽이 없어야함
        route.add((nr1,nc1,nr2,nc2))                             # 방문지점 저장
        if status == 0 : Q.append((nr1,nc1,nr2,nc2,0))           # 가로 상태에서 움직였을 때
        elif status == 1 : Q.append((nr1,nc1,nr2,nc2,1))         # 세로 상태에서 움직였을 때

 

• 가로 상태에서 회전 움직임 확인

 if status == 0 : # 가로
    # 회전 : 왼쪽을 축으로 위
    # 회전 : 왼쪽을 축으로 아래
    # 회전 : 오른쪽을 축으로 위
    # 회전 : 오른쪽을 축으로 아래
    for idx, d in enumerate(((0,0,-1,-1),(0,0,1,-1),(-1,1,0,0),(1,1,0,0))): 
        nr1, nc1, nr2, nc2 = r1 + d[0], c1 + d[1], r2 + d[2], c2 + d[3]
        rotate = 0
        if board[nr1][nc1] == 0 and board[nr2][nc2] == 0:
        	
            # 회전 시 거쳐가는 지점의 벽 여부를 확인
            if idx == 0 and board[r2-1][c2] == 0 : rotate = -1   
            elif idx == 1 and board[r2+1][c2] == 0 : rotate = 1 
            elif idx == 2 and board[r1-1][c1] == 0 : rotate = 1 
            elif idx == 3 and board[r1+1][c1] == 0 : rotate = -1 

            # 가로에서 회전하기 때문에 세로로 변하게 된다.
            # rotate의 값에 따라 좌표를 달리 넣어준다
            
            if rotate == 1:
                route.add((nr1,nc1,nr2,nc2))
                Q.append((nr1,nc1,nr2,nc2,1))

            elif rotate == -1: 
                route.add((nr2,nc2,nr1,nc1))
                Q.append((nr2,nc2,nr1,nc1,1))

 

🎯 최종코드

from collections import deque

def solution(board):
    N = len(board) + 2
    board = [[1] * N ] + [[1] + lst + [1] for lst in board] + [[1] * N] # board의 상하좌우에 벽을 씌어주는과정
    
    time = 0
    robot = deque([(1,1,1,2,0)])        # 초기 로봇 위치,상태
    vi = [[0] * (N) for _ in range(N)]  # 방문표시를 위한 배열
    vi[1][1] = vi[1][2] = 1             # 로봇의 초기 위치방문
    
    def BFS(robot):
        nonlocal time
        robot = deque(set(robot))       # 중복되는 로봇 제거
        Q = deque()                     # 로봇이 1초 동안의 움직임 정보를 담아 놓는 배열
        route = set()                   # 마지막에 방문 표시를 위한 배열
        time += 1                       
        
        while robot:
            r1,c1,r2,c2,status = robot.popleft() # status = > 0 : 가로, 1 : 세로

            for dr1, dc1, dr2, dc2 in ((-1,0,-1,0),(1,0,1,0),(0,-1,0,-1),(0,1,0,1)): # 이동 : 상,하,좌,우
                nr1, nc1, nr2, nc2 = r1 + dr1, c1 + dc1, r2 + dr2, c2 + dc2
                if board[nr1][nc1] == 0 and board[nr2][nc2] == 0:
                    route.add((nr1,nc1,nr2,nc2))
                    if status == 0 : Q.append((nr1,nc1,nr2,nc2,0))
                    elif status == 1 : Q.append((nr1,nc1,nr2,nc2,1))
                    
                    
            if status == 0 : # 가로
                # 회전 : 왼쪽을 축으로 위
                # 회전 : 왼쪽을 축으로 아래
                # 회전 : 오른쪽을 축으로 위
                # 회전 : 오른쪽을 축으로 아래
                for idx, d in enumerate(((0,0,-1,-1),(0,0,1,-1),(-1,1,0,0),(1,1,0,0))): 
                    nr1, nc1, nr2, nc2 = r1 + d[0], c1 + d[1], r2 + d[2], c2 + d[3]
                    rotate = 0
                    if board[nr1][nc1] == 0 and board[nr2][nc2] == 0:
                        if idx == 0 and board[r2-1][c2] == 0 : rotate = -1 
                        elif idx == 1 and board[r2+1][c2] == 0 : rotate = 1 
                        elif idx == 2 and board[r1-1][c1] == 0 : rotate = 1 
                        elif idx == 3 and board[r1+1][c1] == 0 : rotate = -1 

                        if rotate == 1:
                            route.add((nr1,nc1,nr2,nc2))
                            Q.append((nr1,nc1,nr2,nc2,1))

                        elif rotate == -1: 
                            route.add((nr2,nc2,nr1,nc1))
                            Q.append((nr2,nc2,nr1,nc1,1))
                
                
            elif status == 1 : # 세로
                # 회전 : 위쪽을 축으로 왼쪽
                # 회전 : 위쪽을 축으로 오른쪽
                # 회전 : 아래쪽을 축으로 왼쪽
                # 회전 : 아래쪽을 축으로 오른쪽
                for idx, d in enumerate(((0,0,-1,-1),(0,0,-1,1),(1,-1,0,0),(1,1,0,0))):
                    nr1, nc1, nr2, nc2 = r1 + d[0], c1 + d[1], r2 + d[2], c2 + d[3]
                    rotate = 0
                    if board[nr1][nc1] == 0 and board[nr2][nc2] == 0:
                        if idx == 0 and board[r2][c2-1] == 0 : rotate = -1 
                        elif idx == 1 and board[r2][c2+1] == 0 : rotate = 1 
                        elif idx == 2 and board[r1][c1-1] == 0 : rotate = 1 
                        elif idx == 3 and board[r1][c1+1] == 0 : rotate = -1 

                        if rotate == 1:
                            route.add((nr1,nc1,nr2,nc2))
                            Q.append((nr1,nc1,nr2,nc2,0))

                        elif rotate == -1:
                            route.add((nr2,nc2,nr1,nc1))
                            Q.append((nr2,nc2,nr1,nc1,0))
        
        if route :
            for r1,c1,r2,c2 in route:
                vi[r1][c1] = vi[r2][c2] = 1
        
        return Q      
        
    while robot:
        robot = BFS(robot)
        if vi[N-2][N-2] : break
    
    return time