[이코테] BFS - 블록 이동하기

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

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

사고과정

• 로봇 좌표를 하나의 노드, 로봇의 좌표들 간의 비용을 이동하는 데 걸리는 시간(1)으로 간선으로 하여 모든 간선의 비용이 동일할 때 최솟값을 찾는 전형적인 BFS 문제라고 한다.
• 매우 어려웠고 풀지 못했음.. 코드에 좌표를 하나씩 써가면서 풀이를 써놓았으니 소스코드를 참고하는 게 좋을 듯하다.
• 문제풀이의 큰 단계는 다음과 같다. 가장 핵심적인 것은 큐에는 로봇좌표와 간선 비용을 넣는다는 점(이 때 간선 비용을 넣을 때마다 +1 해준다)과 로봇이 이동하거나 회전할 수 있는 경우의 수를 직접 생각해서 그림을 그려봐야 알 수 있다.
• # 1. 맵 정보 벗어나는 걸 간단하게 처리하기 위해 맵 외곽에 벽을 추가로 설치해 늘리기
  # 2. BFS를 활용해야 함. 큐에는 (로봇의 좌표값들, 시간) 형태로 원소를 집어넣음
  # 3. 로봇이 이동 또는 회전이 가능한 경우의 수는 다음과 같음
  # 3-1. 이동하는 경우 -> 상,하,좌,우 이동했을 때, 로봇의 좌표에 있는 값들이 모두 0일 경우
  # 3-2. 회전하는 경우
  # 3-2-1. 로봇이 가로로 되어 있을 경우 -> 로봇 좌표를 기준으로 모두 행+1,-1했을 때 모두 0일 경우가능
  # 3-2-2. 로봇이 세로로 되어 있을 경우 -> 로봇 좌표를 기준으로 모두 열+1,-1했을 때 모두 0일 경우가능

풀이(스스로 못 푼 풀이)

from collections import deque


def move_robot(pos: set, board):
    pos_list = []  # 로봇이 이동가능한 좌표들 담을 리스트
    # 현재 로봇 위치 좌표 값
    pos = list(pos)
    pos_x1, pos_y1, pos_x2, pos_y2 = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
    # 3-1.이동하는 경우
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    for i in range(4):
        pos_next_x1, pos_next_y1, pos_next_x2, pos_next_y2 = pos_x1 + dx[i], pos_y1 + dy[i], pos_x2 + dx[i], pos_y2 + \
                                                             dy[i]
        # 로봇의 좌표에 있는 값들이 모두 0일 경우에는 이동 가능
        if board[pos_next_x1][pos_next_y1] == 0 and board[pos_next_x2][pos_next_y2] == 0:
            pos_list.append({(pos_next_x1, pos_next_y1), (pos_next_x2, pos_next_y2)})
    # 3-2.회전하는 경우
    # 3-2-1. 로봇이 가로로 있는 경우(로봇의 두 좌표 x값이 같을 때)
    if pos_x1 == pos_x2:
        # 위(-1), 아래(+1) 이동하는 경우
        for i in [-1, 1]:
            if board[pos_x1 + i][pos_y1] == 0 and board[pos_x2 + i][pos_y2] == 0:
                pos_list.append({(pos_x1, pos_y1), (pos_x1 + i, pos_y1)})
                pos_list.append({(pos_x2, pos_y2), (pos_x2 + i, pos_y2)})
    # 3-2-2. 로봇이 세로로 있는 경우(로봇의 두 좌표 y값이 같을 때)
    elif pos_y1 == pos_y2:
        # 왼쪽(-1), 오른쪽(+1) 이동하는 경우
        for i in [-1, 1]:
            if board[pos_x1][pos_y1 + i] == 0 and board[pos_x2][pos_y2 + i] == 0:
                pos_list.append({(pos_x1, pos_y1), (pos_x1, pos_y1 + i)})
                pos_list.append({(pos_x2, pos_y2), (pos_x2, pos_y2 + i)})
    # 로봇이 갈 수 있는 위치 좌표 리스트 return
    return pos_list


def solution(board):
    # 1. 맵 길이를 늘리기
    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]
    robot_queue = deque([])  # 로봇 좌표와 시간을 담는 큐 정의
    visited = []  # 로봇이 거쳐간 맵 좌표들 기록(방문 처리용 리스트)
    # 로봇의 초기 위치 정보 넣기
    pos = {(1, 1), (1, 2)}
    robot_queue.append((pos, 0))
    visited.append(pos)
    # 큐가 빌 때까지 BFS 탐색
    while robot_queue:
        pos, cost = robot_queue.popleft()
        # 로봇 위치 좌표 중 하나가 (n, n) 좌표에 도달했다면 종료
        if (n, n) in pos:
            return cost
        # 큐에서 꺼낸 로봇 위치에서 갈 수 있는 곳 탐색
        for next_pos in move_robot(pos, new_board):
            if next_pos not in visited:
                visited.append(next_pos)
                robot_queue.append((next_pos, cost + 1))
    return cost

다음날 혼자 다시 풀어본 풀이

from collections import deque

def move_robot(pos: set, board):
    next_pos_lst = []
    pos = list(pos) # 인덱싱 가능케하기 위해
    pos_x1, pos_y1, pos_x2, pos_y2 = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
    # 1.로봇이 이동가능한지 먼저 탐색
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    for i in range(4):
        next_pos_x1, next_pos_y1, next_pos_x2, next_pos_y2 = pos_x1+dx[i], pos_y1+dy[i], pos_x2+dx[i], pos_y2+dy[i]
        if board[next_pos_x1][next_pos_y1] == 0 and board[next_pos_x2][next_pos_y2] == 0:
            next_pos_lst.append({(next_pos_x1, next_pos_y1), (next_pos_x2, next_pos_y2)})
    # 2-1.로봇이 회전하는 경우 -> 로봇이 가로로 있을 때
    if pos_x1 == pos_x2:
        # 위, 아래 
        for i in [-1, 1]:
            if board[pos_x1+i][pos_y1] == 0 and board[pos_x2+i][pos_y2] == 0:
                next_pos_lst.append({(pos_x1, pos_y1), (pos_x1+i, pos_y1)})
                next_pos_lst.append({(pos_x2, pos_y2), (pos_x2+i, pos_y2)})
    # 2-2.로봇이 회전하는 경우 -> 로봇이 세로로 있을 때
    elif pos_y1 == pos_y2:
        # 위, 아래
        for i in [-1, 1]:
            if board[pos_x1][pos_y1+i] == 0 and board[pos_x2][pos_y2+i] == 0:
                next_pos_lst.append({(pos_x1, pos_y1), (pos_x1, pos_y1+i)})
                next_pos_lst.append({(pos_x2, pos_y2), (pos_x2, pos_y2+i)})
    return next_pos_lst
    

def solution(board):
    n = len(board)
    # 외곽에 벽 추가로 설치 -> 0은 갈 수 있는 칸이므로 벽인 1로 해야함!!
    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]
    pos_q = deque([])   # 로봇 좌표와 비용을 담을 큐 정의
    visited = []     # 방문한 로봇 좌표 담을 리스트
    # 초기 로봇 좌표
    pos = {(1, 1), (1, 2)}
    pos_q.append((pos, 0))
    visited.append(pos)
    # 큐가 빌 때까지 반복
    while pos_q:
        pos, time = pos_q.popleft()
        # 현재 로봇 좌표 중 하나가 (n, n)에 닿았다면 끝!
        if (n, n) in pos:
            break
        # 현재 로봇 좌표 기준으로 로봇이 이동할 수 있는 좌표들 BFS 탐색
        for next_pos in move_robot(pos, new_board):
            if next_pos not in visited:
                visited.append(next_pos) # 방문처리
                pos_q.append((next_pos, time+1)) # 이동가능 로봇 좌표랑 시간+1 해서 큐에 다시 넣기
    return time