[Programmers][Python] 블록 이동하기

April 16, 2025

📝문제 요약

문제 설명

로봇개발자 “무지”는 한 달 앞으로 다가온 “카카오배 로봇경진대회”에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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	result
[[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]]	7

입출력 예에 대한 설명

문제에 주어진 예시와 같습니다.

로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.

✏️문제 풀이

라이브러리 불러오기
```
  from collections import deque
```

필요한 변수 생성

  def solution(board):
  		# 보드의 크기
      n = len(board)
    		
  		# BFS 초기화
      queue = deque()         # BFS를 위한 큐
      visited = []            # 방문한 위치를 저장할 리스트
      pos = {(0, 0), (0, 1)}  # 로봇의 초기 위치 (두 부분의 좌표)
      queue.append((pos, 0))  # 시작 위치와 비용(0)을 큐에 추가
      visited.append(pos)     # 시작 위치를 방문 처리

BFS를 통해 탐색하며 도착지 도달 시 정답 반환

  while queue:
  		# 큐에서 현재 위치와 비용을 꺼냄
      pos, cost = queue.popleft()
    
      # 도착점 (n-1, n-1)에 도달했는지 확인 하여 도착하였다면 현재까지의 비용 반환
      if (n - 1, n - 1) in pos:
          return cost

이동 가능한 방향으로 한 칸씩 이동

  # 다음 위치 계산
  next_pos = []    # 다음에 이동할 수 있는 위치들을 저장할 리스트
  pos = list(pos)  # 집합을 리스트로 변환
        
  # 로봇의 두 부분의 좌표를 각각 저장
  (x1, y1), (x2, y2) = pos[0], pos[1]
        
  # 상, 하, 좌, 우 방향
  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]
        
  # 상하좌우 이동 처리
  for i in range(4):
  		# 로봇의 두 부분 각각의 다음 위치 계산
      nx1, ny1 = x1 + dx[i], y1 + dy[i]
      nx2, ny2 = x2 + dx[i], y2 + dy[i]
            
  		# 다음 위치가 보드 범위 내에 있는지 확인
      if 0 <= nx1 < n and 0 <= ny1 < n and 0 <= nx2 < n and 0 <= ny2 < n:
  		    # 다음 위치가 모두 이동 가능하다면 next_pos에 추가
          if board[nx1][ny1] == 0 and board[nx2][ny2] == 0:
              next_pos.append({(nx1, ny1), (nx2, ny2)})

회전이 가능한 경우, 회전한 위치도 next_pos에 추가

  # 가로 방향일 때
  if x1 == x2:  
  		# 위(-1) or 아래(1)로 회전
      for i in [-1, 1]:  
  		    # 회전 가능한지 확인
          if 0 <= x1 + i < n and 0 <= x2 + i < n:
  		        # 회전 시 필요한 공간이 비어있는지 확인
              if board[x1 + i][y1] == 0 and board[x2 + i][y2] == 0:
                  next_pos.append({(x1, y1), (x1 + i, y1)})  # 첫 번째 부분을 기준으로 회전
                  next_pos.append({(x2, y2), (x2 + i, y2)})  # 두 번째 부분을 기준으로 회전
        
  # 세로 방향일 때
  elif y1 == y2:
  		# 왼쪽(-1) or 오른쪽(1)으로 회전
      for i in [-1, 1]:  
  		    # 회전 가능한지 확인
          if 0 <= y1 + i < n and 0 <= y2 + i < n:
  		        # 회전 시 필요한 공간이 비어있는지 확인
              if board[x1][y1 + i] == 0 and board[x2][y2 + i] == 0:
                  next_pos.append({(x1, y1), (x1, y1 + i)})  # 첫 번째 부분을 기준으로 회전
                  next_pos.append({(x2, y2), (x2, y2 + i)})  # 두 번째 부분을 기준으로 회전

이동할 수 있는 위치 중 아직 방문하지 않은 곳만 큐에 추가

  # 다음 위치들에 대해 BFS 진행
  for next_p in next_pos:
  		# 아직 방문하지 않은 위치라면 큐에 추가하고 방문 처리
      if next_p not in visited:
          queue.append((next_p, cost + 1))
          visited.append(next_p)

도착하지 못했을 경우 0을 반환
```
  return 0
```

💯제출 코드

from collections import deque

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

    queue = deque()
    visited = []
    pos = {(0, 0), (0, 1)}
    queue.append((pos, 0))
    visited.append(pos)
    
    while queue:
        pos, cost = queue.popleft()
        if (n-1, n-1) in pos:
            return cost
        
        next_pos = []
        pos = list(pos)
        pos1_x, pos1_y, pos2_x, pos2_y = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
        
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        
        for i in range(4):
            pos1_next_x, pos1_next_y = pos1_x + dx[i], pos1_y + dy[i]
            pos2_next_x, pos2_next_y = pos2_x + dx[i], pos2_y + dy[i]
            
            if 0 <= pos1_next_x < n and 0 <= pos1_next_y < n and 0 <= pos2_next_x < n and 0 <= pos2_next_y < n:
                if board[pos1_next_x][pos1_next_y] == 0 and board[pos2_next_x][pos2_next_y] == 0:
                    next_pos.append({(pos1_next_x, pos1_next_y), (pos2_next_x, pos2_next_y)})
        
        if pos1_x == pos2_x:
            for i in [-1, 1]:
                if 0 <= pos1_x + i < n and 0 <= pos2_x + i < n:
                    if board[pos1_x + i][pos1_y] == 0 and board[pos2_x + i][pos2_y] == 0:
                        next_pos.append({(pos1_x, pos1_y), (pos1_x + i, pos1_y)})
                        next_pos.append({(pos2_x, pos2_y), (pos2_x + i, pos2_y)})
        else:
            for i in [-1, 1]:
                if 0 <= pos1_y + i < n and 0 <= pos2_y + i < n:
                    if board[pos1_x][pos1_y + i] == 0 and board[pos2_x][pos2_y + i] == 0:
                        next_pos.append({(pos1_x, pos1_y), (pos1_x, pos1_y + i)})
                        next_pos.append({(pos2_x, pos2_y), (pos2_x, pos2_y + i)})
        
        for next_pos in next_pos:
            if next_pos not in visited:
                queue.append((next_pos, cost + 1))
                visited.append(next_pos)
    
    return 0

Lee Hyun Ji

[Programmers][Python] 블록 이동하기

📝문제 요약

문제 설명

제한사항

입출력 예

입출력 예에 대한 설명

✏️문제 풀이

💯제출 코드

댓글남기기

참고

[백준][Python] 1302. 베스트셀러

[TIL] 2025.04.19 - Today I Learn

[Programmers][MySQL] 노선별 평균 역 사이 거리 조회하기

[백준][Python] 10867. 중복 빼고 정렬하기