|
| 1 | +from collections import deque |
| 2 | + |
| 3 | +def get_next_pos(pos, board): |
| 4 | + next_pos = [] # 반환 결과 (이동 가능한 위치들) |
| 5 | + pos = list(pos) # 현재 위치 |
| 6 | + pos1_x, pos1_y, pos2_x, pos2_y = pos[0][0], pos[0][1], pos[1][0], pos[1][1] |
| 7 | + # (상, 하, 좌, 우)로 이동하는 경우에 대해서 처리 |
| 8 | + dx = [-1, 1, 0, 0] |
| 9 | + dy = [0, 0, -1, 1] |
| 10 | + for i in range(4): |
| 11 | + pos1_next_x, pos1_next_y, pos2_next_x, pos2_next_y = pos1_x + dx[i], pos1_y + dy[i], pos2_x + dx[i], pos2_y + dy[i] |
| 12 | + # 이동하고자 하는 두 칸이 모두 비어있다면 |
| 13 | + if board[pos1_next_x][pos1_next_y] == 0 and board[pos2_next_x][pos2_next_y] == 0: |
| 14 | + next_pos.append({(pos1_next_x, pos1_next_y), (pos2_next_x, pos2_next_y)}) |
| 15 | + # 현재 로봇이 가로로 놓여 있는 경우 |
| 16 | + if pos1_x == pos2_x: |
| 17 | + for i in [-1, 1]: # 위쪽으로 회전하거나, 아래쪽으로 회전 |
| 18 | + if board[pos1_x + i][pos1_y] == 0 and board[pos2_x + i][pos2_y] == 0: # 위쪽 혹은 아래쪽 두 칸이 모두 비어 있다면 |
| 19 | + next_pos.append({(pos1_x, pos1_y), (pos1_x + i, pos1_y)}) |
| 20 | + next_pos.append({(pos2_x, pos2_y), (pos2_x + i, pos2_y)}) |
| 21 | + # 현재 로봇이 세로로 놓여 있는 경우 |
| 22 | + elif pos1_y == pos2_y: |
| 23 | + for i in [-1, 1]: # 왼쪽으로 회전하거나, 오른쪽으로 회전 |
| 24 | + if board[pos1_x][pos1_y + i] == 0 and board[pos2_x][pos2_y + i] == 0: # 왼쪽 혹은 오른쪽 두 칸이 모두 비어 있다면 |
| 25 | + next_pos.append({(pos1_x, pos1_y), (pos1_x, pos1_y + i)}) |
| 26 | + next_pos.append({(pos2_x, pos2_y), (pos2_x, pos2_y + i)}) |
| 27 | + # 현재 위치에서 이동할 수 있는 위치를 반환 |
| 28 | + return next_pos |
| 29 | + |
| 30 | +def solution(board): |
| 31 | + # 맵의 외곽에 벽을 두는 형태로 맵 변형 |
| 32 | + n = len(board) |
| 33 | + new_board = [[1] * (n + 2) for _ in range(n + 2)] |
| 34 | + for i in range(n): |
| 35 | + for j in range(n): |
| 36 | + new_board[i + 1][j + 1] = board[i][j] |
| 37 | + # 너비 우선 탐색(BFS) 수행 |
| 38 | + q = deque() |
| 39 | + visited = [] |
| 40 | + pos = {(1, 1), (1, 2)} # 시작 위치 설정 |
| 41 | + q.append((pos, 0)) # 큐에 삽입한 뒤에 |
| 42 | + visited.append(pos) # 방문 처리 |
| 43 | + # 큐가 빌 때까지 반복 |
| 44 | + while q: |
| 45 | + pos, cost = q.popleft() |
| 46 | + # (n, n) 위치에 로봇이 도달했다면, 최단 거리이므로 반환 |
| 47 | + if (n, n) in pos: |
| 48 | + return cost |
| 49 | + # 현재 위치에서 이동할 수 있는 위치 확인 |
| 50 | + for next_pos in get_next_pos(pos, new_board): |
| 51 | + # 아직 방문하지 않은 위치라면 큐에 삽입하고 방문 처리 |
| 52 | + if next_pos not in visited: |
| 53 | + q.append((next_pos, cost + 1)) |
| 54 | + visited.append(next_pos) |
| 55 | + return 0 |
0 commit comments