문제 설명
로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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으로 주어집니다.
- 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.
* 모든 간선의 비용이 1로 동일할 경우에는 BFS 를 이용해 최적의 해를 구할 수 있다!!!!
* 아래 풀이는 <이것이 코딩테스트다> 에 기록된 답안입니다.
풀이
from collections import deque
def get_next_pos(pos, board): # 다음에 이동할 수 있는 위치 리턴
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,0,-1,0]
dy = [0,1,0,-1]
for i in range(4) :
next_pos1_x = pos1_x + dx[i]
next_pos1_y = pos1_y + dy[i]
next_pos2_x = pos2_x + dx[i]
next_pos2_y = pos2_y + dy[i]
# 이동할 칸이 모두 비어있다면
if board[next_pos1_x][next_pos1_y] == 0 and board[next_pos2_x][next_pos2_y] == 0 :
next_pos.append({(next_pos1_x,next_pos1_y),(next_pos2_x,next_pos2_y)})
if pos1_x == pos2_x : # 가로로 놓여있다면
for i in [-1,1] :
# 대각선과 이동할 칸이 모두 비어있다면
if board[pos1_x+i][pos1_y] == 0 and board[pos2_x+i][pos2_y] == 0 :
next_pos.append({(pos1_x+i,pos1_y),(pos1_x, pos1_y)})
next_pos.append({(pos2_x+i,pos2_y),(pos2_x,pos2_y)})
elif pos1_y == pos2_y : # 세로로 놓여있다면
for i in [-1,1] :
# 대각선과 이동할 칸이 모두 비어있다면
if board[pos1_x][pos1_y+i] == 0 and board[pos2_x][pos2_y+i] == 0 :
next_pos.append({(pos1_x,pos1_y+i),(pos1_x, pos1_y)})
next_pos.append({(pos2_x,pos2_y+i),(pos2_x,pos2_y)})
return next_pos
def solution(board):
n = len(board)
arr = [[1]*(n+2) for _ in range(n+2)]
for i in range(n):
for j in range(n) :
arr[i+1][j+1] = board[i][j]
visited = []
pos = {(1,1),(1,2)} # 시작위치. 집합으로 표시해 순서상관없이 처리
q = deque([])
q.append((pos, 0))
visited.append(pos)
while q : # BFS 실행
pos, time = q.popleft()
if (n,n) in pos : # 현재 위치가 (n,n) 이라면
return time # 소요시간 리턴
for next_pos in get_next_pos(pos, arr) :
if next_pos not in visited : # 다음 위치를 방문하지 않았다면
q.append((next_pos, time+1)) # 큐에 삽입
visited.append(next_pos) # 방문 처리
return 0
- 로봇이 차지하고 있는 칸이 두 칸이기 때문에, 이를 집합 형태로 관리하면 된다!
- 집합의 경우, 순서가 없기 때문에 해당 칸의 방문여부를 확인하는 visited[] 에서 사용할 수 있다.
- 즉, {(1,1),(2,1)} 을 방문했을 때 {(2,1),(1,1)} 또한 당연히 같은 집합으로 간주하므로 방문한 것이다.
- 그러나 {(1,1),(1,2)} 의 경우, 엄연히 다른 객체로 방문하지 않은 칸으로, 로봇이 이동할 수 있다.
- 로봇의 칸을 집합으로 처리하는 것만 제외하면 나머지는 보통의 BFS 과정과 동일하다.
- 또한, 로봇이 상하좌우 혹은 90도 회전으로 이동할 수 있는 모든 경우들을 get_next_pos() 함수로 계산한다.
- get_next_pos()
- 현재 좌표에서 상하좌우로 이동할 칸이 모두 0 으로 비어있다면 이동할 수 있음으로 next_pos[] 에 추가한다.
- 현재 로봇이 가로로 놓여있을 경우 90도 회전할 수 있는 경우는 2개이다.
- 현재 로봇이 세로로 놓여있을 경우 90도 회전할 수 있는 경우는 2개이다.
- 각 경우에 회전할 주축의 대각선이 비어있고, 회전할 좌표가 모두 0으로 비어있다면 next_post[] 에 추가한다
- next_pos() 에서 리턴받은 좌표들을 방문하지 않았다면 (not in visited) , 해당 좌표를 방문하고 큐에 삽입한다.
'알고리즘 > DFS, BFS' 카테고리의 다른 글
[백준] 19236번: 청소년 상어 - 파이썬(python) (0) | 2022.10.24 |
---|---|
[백준] 16236번: 아기 상어 - 파이썬(python) (0) | 2022.10.24 |
[백준] 16234번: 인구 이동 - 파이썬(python) (0) | 2022.10.08 |
[백준] 18428번: 감시 피하기 - 파이썬(python) (0) | 2022.10.07 |
[백준] 14888번: 연산자 끼워넣기 - 파이썬(python) (0) | 2022.10.07 |
댓글