프로그래머스-블록 이동하기

문제

블록 이동하기 (2020카카오공채)

풀이

문제조건 해석

로봇은 왼쪽, 오른쪽 발 있다.

이동 / 회전 조건에 따라서 블록을 움직이면서 목표 위치까지 도달하는 최소시간 구하기

• 이동 조건 : 상하좌우 이동 가능, 왼쪽 또는 오른쪽 발에 벽이 있으면 이동 불가능
• 회전 조건 : 90도 회전 가능, 회전 결과에 벽이 있거나 회전 중에 벽에 부딪히면 이동 불가능
  • 왼쪽 축을 기준으로 90도 회전하는 2가지 경우 존재
  • 오른쪽 축을 기준으로 90도 회전하는 2가지 경우 존재

알고리즘

BFS + 복잡한 조건 이용해서 구현했다.

왼쪽 축과 오른쪽 축을 구분해서 회전시켜주었는데, 양 축이 조건에 맞게 지정되었는지 확인해 주어야 한다.

• 왼쪽 축은 항상 오른쪽 축보다 왼쪽에 있거나, 아래에 있어야 함

코드

from collections import deque


def bfs(board):
    n = len(board)
    queue = deque([((0, 0), (0, 1))])
    visited = {((0, 0), (0, 1))}
    time = 0
    while queue:
        for _ in range(len(queue)):
            left, right = queue.popleft()
            li, lj = left
            ri, rj = right
            if (li, lj) == (n - 1, n - 1) or (ri, rj) == (n - 1, n - 1):
                return time
            # 이동
            for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                if not (0 <= li + di < n and 0 <= ri + di < n and
                        0 <= lj + dj < n and 0 <= rj + dj < n):
                    continue
                if not (board[li + di][lj + dj] or board[ri + di][rj + dj]) and \
                        ((li + di, lj + dj), (ri + di, rj + dj)) not in visited:
                    visited.add(((li + di, lj + dj), (ri + di, rj + dj)))
                    queue.append(((li + di, lj + dj), (ri + di, rj + dj)))
            # 회전
            # 가로로 위치해 있을때
            if li == ri:
                if lj > rj:  # 왼쪽 축이 오른쪽 축보다 오른쪽에 있다면
                    li, lj, ri, rj = ri, rj, li, lj
                # 왼쪽 축으로 해서 회전
                for di, dj in [(-1, -1), (1, -1)]:
                    if not (0 <= ri + di < n and 0 <= rj + dj < n):
                        continue
                    if board[ri + di][rj]:  # 회전 중 벽에 충돌
                        continue
                    if not board[ri + di][rj + dj] and ((li, lj), (ri + di, rj + dj)) not in visited:
                        visited.add(((li, lj), (ri + di, rj + dj)))
                        queue.append(((li, lj), (ri + di, rj + dj)))
                # 오른쪽 축으로 회전
                for di, dj in [(-1, 1), (1, 1)]:
                    if not (0 <= li + di < n and 0 <= lj + dj < n):
                        continue
                    if board[li + di][lj]:
                        continue
                    if not board[li + di][lj + dj] and ((li + di, lj + dj), (ri, rj)) not in visited:
                        visited.add(((li + di, lj + dj), (ri, rj)))
                        queue.append(((li + di, lj + dj), (ri, rj)))
            # 세로로 위치해 있을 때
            elif lj == rj:
                if li < ri:  # 왼쪽 축이 오른쪽 축보다 위쪽에 위치한다면
                    li, lj, ri, rj = ri, rj, li, lj
                # 아래 축으로 해서 회전
                for di, dj in [(1, -1), (1, 1)]:
                    if not (0 <= ri + di < n and 0 <= rj + dj < n):
                        continue
                    if board[ri][rj + dj]:  # 회전 중 벽에 충돌
                        continue
                    if not board[ri + di][rj + dj] and ((li, lj), (ri + di, rj + dj)) not in visited:
                        visited.add(((li, lj), (ri + di, rj + dj)))
                        queue.append(((li, lj), (ri + di, rj + dj)))
                # 위쪽 축으로 회전
                for di, dj in [(-1, -1), (-1, 1)]:
                    if not (0 <= li + di < n and 0 <= lj + dj < n):
                        continue
                    if board[li][lj + dj]:
                        continue
                    if not board[li + di][lj + dj] and ((li + di, lj + dj), (ri, rj)) not in visited:
                        visited.add(((li + di, lj + dj), (ri, rj)))
                        queue.append(((li + di, lj + dj), (ri, rj)))
        time += 1


def solution(board):
    return bfs(board)

배운점

• 무작정 조건에 따라 분기하면 예외 상황 발생하기 쉽다.
• 디버깅은 시간이 더 소요되니 처음에 잘 생각해서 코딩하자.