[Programmers/프로그래머스] 2020 KAKAO BLIND RECRUITMENT [코딩테스트]

1. [Lv. 2] 문자열 압축
2. [Lv. 2] 괄호 변환
3. [Lv. 3] 자물쇠와 열쇠
4. [Lv. 4] 가사 검색
5. [Lv. 3] 기둥과 보 설치
6. [Lv. 3] 외벽 점검
7. [Lv. 3] 블록 이동하기

📌 문제

📝 제한사항

💻 입출력 예

📖 입출력 예에 대한 설명

📌 풀이

from collections import deque

def get_next_position(position, board):
    next_position = []      # 이동 및 회전 가능한 모든위치
    x1, y1 = list(position)[0]    # 로봇의 현재위치1, unpack을 위해 집합자료형 리스트로 변환
    x2, y2 = list(position)[1]    # 로봇의 현재위치2, unpack을 위해 집합자료형 리스트로 변환

    # 현재위치로부터 이동가능한 모든위치 탐색, 중복방지를 위해 집합자료형으로 관리
    dx = [-1, 1, 0, 0]      # 상하좌우순
    dy = [0, 0, -1, 1]      # 상하좌우순
    for i in range(4):                          # 상하좌우 각 4개의 방향에 대해
        nx1, ny1 = x1 + dx[i], y1 + dy[i]       # 로봇의 다음위치1
        nx2, ny2 = x2 + dx[i], y2 + dy[i]       # 로봇의 다음위치2
        if board[nx1][ny1] == 0 and board[nx2][ny2] == 0:   # 다음위치가 지도밖을 벗어나지 않거나, 벽이 없다면
            next_position.append({(nx1, ny1), (nx2, ny2)})  # 이동가능한 모든위치에 다음위치 추가

    # 현재위치로부터 회전가능한 모든위치 탐색, 중복방지를 위해 집합자료형으로 관리
    if x1 == x2:                                            # 로봇이 가로로 위치한 경우
        for i in [-1, 1]:                                       # 아래쪽 회전반경, 위쪽 회전반경
            if board[x1 + i][y1] == 0 and board[x2 + i][y2] == 0:   # 각 회전반경에 벽이 없다면
                next_position.append({(x1, y1), (x1 + i, y1)})      # 왼축을 기준으로 회전한 경우 추가
                next_position.append({(x2, y2), (x2 + i, y2)})      # 오른축을 기준으로 회전한 경우 추가
    elif y1 == y2:                                          # 로봇이 세로로 위치한 경우
        for i in [-1, 1]:                                       # 왼쪽 회전반경, 오른쪽 회전반경
            if board[x1][y1 + i] == 0 and board[x2][y2 + i] == 0:   # 각 회전반경에 벽이 없다면
                next_position.append({(x1, y1), (x1, y1 + i)})      # 윗축을 기준으로 회전한 경우 추가
                next_position.append({(x2, y2), (x2, y2 + i)})      # 아랫축을 기준으로 회전한 경우 추가

    return next_position

def solution(board):
    n = len(board)

    # 지도 밖을 벗어나는 범위조건을 쉽게 확인하기 위해, 테두리를 1로 감싸는 작업
    new_board = [[1] * (n + 2) for _ in range(n + 2)]
    for row in range(n):
        for col in range(n):
            new_board[row + 1][col + 1] = board[row][col]

    # BFS
    visited = []
    start = {(1, 1), (1, 2)}        # 로봇 시작위치, 중복방지를 위해 집합자료형으로 관리
    visited.append(start)           # 로봇 방문기록
    queue = deque([(start, 0)])     # [현재위치, 걸린시간]
    while queue:
        position, cost = queue.popleft()    # 현재위치, 걸린시간
        if (n, n) in position:              # 목표지점에 도달했다면
            return cost                         # 걸린시간 반환
        for next_position in get_next_position(position, new_board):    # 이동 및 회전 가능한 다음위치에 대해
            if next_position not in visited:                        # 방문한적 없는 위치라면
                visited.append(next_position)                       # 방문기록 후
                queue.append((next_position, cost + 1))             # 큐에 추가

    return 0