[프로그래머스] 2020 KAKAO 블록 이동하기 (파이썬)

문제 설명

---

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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 함수를 완성해주세요.

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

 

문제풀이

---

최소 시간을 구하라고 하고 좌표 이동이니, BFS를 사용하기로 생각했다.

근데 로봇의 크기는 2였는데 항상 1인걸로 풀다보니까 2를 어떻게 처리할까 고민했는데 그냥 끝자리 (로봇이 마지막에 차지하는 부분)을 que에 넣고 자리 이동을 하기로 생각했다. 그리고 벽 1에 닿거나 범위를 초과하면 안된다고 조건을 달고 만약 그 조건을 만족하지 않을때 (else이면) 90도로 회전을 하기로 생각했다. turn 함수를 만들었다

 

1차시도

from collections import deque

def solution(board):
    answer = 0
    direction = 0
    n=len(board)
    visited = [[-1]*n for _ in range(n)] #방문 안한거
    print(visited)
    def turn(direction):
        direction = (direction+1) %4
        return direction
    
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    
    que = deque()
    
    que.append((0,1)) #끝 부분만 기록
    visited[0][1]=0
    while que:
        x, y = que.popleft()
        nx = x + dx[direction]
        ny = y + dy[direction]
        
        if 0<=nx<n and 0<=ny<n and board[nx][ny]==0:
            if visited[nx][ny]==-1:
                answer+=1 #초 세기
                que.append((nx, ny))
                visited[nx][ny]=0
        else: #방향을 바꾸어보기
            while True:
                direction=turn(direction)
                nx = x + dx[direction]
                ny = y + dy[direction]
                if 0<=nx<n and 0<=ny<n and board[nx][ny]==0:
                    if visited[nx][ny]==-1:
                        answer+=1 #초 세기
                        que.append((nx, ny))
                        visited[nx][ny]=0
                        break
    print(answer)
    return answer

결과는 시간초과로 실패.

일단 시도는 좋았으나 아마 크기가 2인 로봇처리, 90도로 시계방향, 반시계방향 회전할 때 처리하는 게 문제가 있는 듯하다.

 

결론은 로봇의 두 칸을 모두 고려하지 않고, 끝 부분만 기록하고 있어서 정답이 안되는 것이었다!

로봇이 두 칸을 차지하므로, 현재 위치뿐 아니라 상태(가로 또는 세로)를 함께 기록해야 한다.

 

최소 시간을 구할 때는 que에 위치 뿐만 아니라 시간도 같이 넣자

나는 일일히 cnt를 해서 최소경로가 아닐 수도 있고 모든 경우의 수를 생각하지 못하게 된다.

 

1. 크기가 2인 로봇이 현재 위치하고 있는 좌표 2개와 시간을 동시에 que에 넣었다.

    (시간을 일일이 cnt하는 것이 아닌 모든 경우의 수를 생각해야 하기 때문에 que에 넣어야 한다)

2. 회전을 하기에 로봇이 가로, 세로를 고려해야 한다.

   (가로에 위치하고 있을 때 위쪽,아래 회전이 있고 세로에 위치하고 있을 때 위쪽 아래쪽 회전이 있다)

 

*회전을 할 때 중요한 점은 회전 결과에서 위치하고 있는 위치가 0일 뿐만이 아니라 회전을 할 때 지나는 위치도 0 이어야한다는 점*

bfs

 

그러면 코드를 다시 짜보기 (2차시도)

설명은 주석으로 달았다.

 

정답

#bfs 이용
from collections import deque
def solution(board):
    n = len(board)
    
    start = ((0, 0), (0, 1))  # 로봇의 초기 위치 (0,0)을 (1,1)로 변경
    visited = set([start])  # 로봇이 방문했던 위치
    goal = (n-1, n-1)  # 목표 위치
    que = deque()
    que.append((start, 0))  # 큐에 로봇의 위치와 시간을 같이 넣어준다
    
    def is_valid(pos1, pos2):  # 범위 확인해주는 함수
        x1, y1 = pos1
        x2, y2 = pos2
        return 0 <= x1 < n and 0 <= y1 < n and 0 <= x2 < n and 0 <= y2 < n and board[x1][y1] == 0 and board[x2][y2] == 0
    
    # 상하좌우 위치
    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while que:
        (pos1, pos2), time = que.popleft()
        if pos1 == goal or pos2 == goal:
            return time
        
        x1, y1 = pos1
        x2, y2 = pos2
        
        # 이동
        for dx, dy in direction:
            nx1, ny1 = x1 + dx, y1 + dy
            nx2, ny2 = x2 + dx, y2 + dy
            if is_valid((nx1, ny1), (nx2, ny2)) and ((nx1, ny1), (nx2, ny2)) not in visited:
                visited.add(((nx1, ny1), (nx2, ny2)))  # 방문처리
                que.append((((nx1, ny1), (nx2, ny2)), time + 1))
        
        # 회전
        if x1 == x2:  # 가로로 놓여있는 경우
            for i in [-1, 1]:  # 행을 기준으로 아래로 회전, 위로 회전 (x+1 또는 x-1)
                if 0 <= x1 + i < n and 0 <= x2 + i < n and board[x1 + i][y1] == 0 and board[x2 + i][y2] == 0:
                    if ((x1, y1), (x1 + i, y1)) not in visited:  # 왼쪽을 축으로 회전
                        visited.add(((x1, y1), (x1 + i, y1)))
                        que.append((((x1, y1), (x1 + i, y1)), time + 1))
                    if ((x2, y2), (x2 + i, y2)) not in visited:  # 오른쪽을 축으로 회전
                        visited.add(((x2, y2), (x2 + i, y2)))
                        que.append((((x2, y2), (x2 + i, y2)), time + 1))
        elif y1 == y2:  # 세로로 놓여있는 경우
            for i in [-1, 1]:
                if 0 <= y1 + i < n and 0 <= y2 + i < n and board[x1][y1 + i] == 0 and board[x2][y2 + i] == 0:
                    if ((x1, y1), (x1, y1 + i)) not in visited:  # 위쪽을 축으로 회전
                        visited.add(((x1, y1), (x1, y1 + i)))
                        que.append((((x1, y1), (x1, y1 + i)), time + 1))
                    if ((x2, y2), (x2, y2 + i)) not in visited:  # 아래쪽을 축으로 회전
                        visited.add(((x2, y2), (x2, y2 + i)))
                        que.append((((x2, y2), (x2, y2 + i)), time + 1))
                        
    return -1

 

주의할거.. 튜플로 인자를 넣어주기에 visited에도, que에도 괄호로 잘 묶어주자