[카카오/파이썬] 블록 이동하기

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

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

 

결국 BFS를 이동해서 로봇이 (n,n)에 도달할때까지의 최단거리를 구한다.

1. 벽을 하나 둘러싼 모양으로 확장된 보드를 만들어서 (1,1) ~ (n,n) 이라고 생각하기 쉽게 해준다.

2. 갈수있는 위치를 구하는 함수는 갈수 있는 위치의 리스트를 리턴한다.

3. 갈수 있는 위치는 queue에 넣고, 방문하면 visited에 넣는다. 일반적인 bfs로 , 큐가 빌 때까지 반복한다.

4. 갈 수 있는 위치 : 나란히 있는 두 칸이 둘다 0일때, 상하좌우 이동해서도 두 칸이 모두 0일떄, 회전을 가로축을 중심으로 할 때와 세로축을 중심으로 할 때를 알아봐야 한다. 

가로방향으로 놓여있었을 때 : x좌표끼리 같을때

세로방향으로 놓여있었을 때 : y 좌표끼리 같을 때

 

앞으로 로봇에 갈 수 있는 위치를 구하는 측면에서 조건에 따라서 회전을 구현해주어야 한다는 것과, 상하좌우로 이동하되 로봇이 차지 하는 좌표는 2개이므로 이걸 고려해야 한다 -> 좌표 2개를 하나의 튜플로 묶어서 생각한다 ! 

from collections import deque

def get_next_pos(pos, board):
    next_pos = []
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    pos = list(pos)
    pos1_x, pos1_y, pos2_x, pos2_y = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
    
    for i in range(4):
        pos1_next_x, pos1_next_y, pos2_next_x, pos2_next_y = pos1_x + dx[i], pos1_y + dy[i], pos2_x + dx[i], pos2_y + dy[i]   
        # 이동하고자 하는 두 칸이 모두 비어있다면
        if board[pos1_next_x][pos1_next_y] == 0 and board[pos2_next_x][pos2_next_y] == 0:
            next_pos.append({(pos1_next_x, pos1_next_y),(pos2_next_x, pos2_next_y)})
    
    # 현재 로봇이 가로로 놓여있는 경우
    if pos1_x == pos2_x:
        for i in [1, -1]:
            if board[pos1_x + i][pos1_y] == 0 and board[pos2_x + i][pos2_y] == 0:
                next_pos.append({(pos1_x, pos1_y), (pos1_x+i, pos1_y)})
                next_pos.append({(pos2_x, pos2_y),(pos2_x+i, pos2_y)})
    elif pos1_y == pos2_y:
        for i in [1, -1]:
            if board[pos1_x][pos1_y + i] == 0 and board[pos2_x][pos2_y+i] == 0:
                next_pos.append({(pos1_x, pos1_y),(pos1_x, pos1_y + i)})
                next_pos.append({(pos2_x, pos2_y),(pos2_x, pos2_y + i)})
    
    # 현재 로봇이 세로로 놓여 있는 경우 
    return next_pos


def solution(board):
    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()
    visited = []
    pos = {(1,1), (1,2)}
    q.append((pos, 0)) # pos, cost
    visited.append(pos)
    
    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:
                q.append((next_pos, cost+1))
                visited.append(next_pos)
        
        
    return answer