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

문제 <블록 이동하기>

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.

로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.

로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.

"0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

---

입출력

• board = [[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]]
• result = 7

---

풀이

• 각각의 회전과 평행이동 후 결과를 큐에 저장하면 된다고 생각해 문제를 풀었지만,
• 회전 시 로봇의 두 칸 모두 축이 될 수 있다는 것을 생각하면 경우의 수가 너무 많아졌고, 방문시 어떤 좌표를 기준으로 확인해야 할지 의문이 생겼다.
• 회전과 평행이동을 각 방향으로 모두 생각할 때 시간 코드를 효율적으로 작성하기 어려워 결국 시간 안에 해결하지 못했다.

from collections import deque

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def next_pos(pos, board):   # 다음 위치 가져오기
    next = []
    (x1, y1), (x2, y2) = pos    # 현재 위치
    for i in range(4):      # 평행 이동
        nx1, ny1 = x1 + dx[i], y1 + dy[i]
        nx2, ny2 = x2 + dx[i], y2 + dy[i]
        if board[nx1][ny1] == board[nx2][ny2] == 0:
            next.append({(nx1, ny1), (nx2, ny2)})
    if x1 == x2:       # 가로일 때 회전
        for i in [1, -1]:
            if board[x1 + i][y1] == board[x2 + i][y2] == 0:
                next.append({(x1, y1), (x1 + i, y1)})
                next.append({(x2, y2), (x2 + i, y2)})
    elif y1 == y2:      # 세로일 때 회전
        for i in [1, -1]:
            if board[x1][y1 + i] == board[x2][y2 + i] == 0:
                next.append({(x1, y1), (x1, y1 + i)})
                next.append({(x2, y2), (x2, y2 + i)})
    return next


def solution(board):
    answer = 0
    N = len(board)
    new_board = [[1] * (N + 2) for _ in range(N + 2)]   # board를 양쪽으로 한 칸씩 늘려 예외처리 단순화
    for i in range(N):
        for j in range(N):
            new_board[i + 1][j + 1] = board[i][j]
    q = deque()
    pos = {(1, 1), (1, 2)}     # 집합 자료형으로 관리
    q.append((pos, 0))
    visit = []
    visit.append(pos)
    while q:    
        pos, t = q.popleft()
        if (N, N) in pos:   # (N, N) 위치까지 이동했을 때
            return t
        for n in next_pos(pos, new_board):  # 함수를 통해 다음 위치를 가져오기
            if n not in visit:
                visit.append(n)
                q.append((n, t+1))

알고리즘을 코드로 구현하기 까다로운 문제였다.

해당 로봇의 8가지 경우의 회전을 정리된 코드로 구현하지 못하였고, 방문 여부를 확인하기 위한 visit에 각각의 좌표를 넣어서 확인할 때 제한 시간이 초과하지 않을까 생각해 다른 방법으로 구현을 시도했다.

 

다른 사람의 풀이를 참고하니 위치 정보를 담는 pos는 집합 자료형으로 설정해 순서가 바뀌었을 때도 방문 확인을 할 수 있도록 만들어 주었다.

---

해당 문제를 통해 시간 복잡도를 줄일 수 있는 집합 자료형에 대한 정리가 필요하다는 것을 느꼈다.

생각한 알고리즘을 정확하게 검증하고, 시간 복잡도를 고려한 구현 방법을 결정한 후 코드를 작성하는 연습이 필요하다.

 

 

 

 

 

 

프로그래머스