프로그래머스, 2020 카카오 공채 코딩테스트 기출 - 블록 이동하기 LV3
https://programmers.co.kr/learn/courses/30/lessons/60063
BFS, 회전처리가 까다로운 문제
0과 1로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.
입출력 예
board result [[0, 0, 0, 1, 1], 7 [0, 0, 0, 1, 0], [0, 1, 0, 1, 1], [1, 1, 0, 0, 1], [0, 0, 0, 0, 0]]
문제에 주어진 예시와 같습니다.
로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.
솔루션
BFS 탐색으로 que를 사용하여 이동/회전 할수 있는 경우를
can_move에 저장하고 confirm으로 방문했던 경우인지 확인한다.
방문하지 않았다면 넣을 때 이동수를 count를 1씩 추가해서 큐에 넣어준다. cur1이나 cur2가 (N,N)일 때 count를 return 한다.
회전하는 경우 가로방향일때는 위/아래에 1이 하나라도 있으면 해당 방향 회전이 불가능하고, 세로방향일때는 왼쪽/오른쪽에 1이 하나라도 있으면 해당 방향 회전이 불가능하다는 것을 이용하여 푼다.
# board 외벽으로 둘러싼 후 new_board로 예외 처리
[[1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1],
[1, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1]]
코드
# 파이썬
from collections import deque
def can_move(cur1, cur2, new_board):
Y, X = 0, 1
cand = []
# 평행이동
DELTAS = [(-1, 0), (1, 0), (0, 1), (0, -1)]
for dy, dx in DELTAS:
nxt1 = (cur1[Y] + dy, cur1[X] + dx)
nxt2 = (cur2[Y] + dy, cur2[X] + dx)
if new_board[nxt1[Y]][nxt1[X]] == 0 and new_board[nxt2[Y]][nxt2[X]] == 0:
cand.append((nxt1, nxt2))
# 회전
if cur1[Y] == cur2[Y]: # 가로방향 일 때
UP, DOWN = -1, 1
for d in [UP, DOWN]:
if new_board[cur1[Y]+d][cur1[X]] == 0 and new_board[cur2[Y]+d][cur2[X]] == 0:
cand.append((cur1, (cur1[Y]+d, cur1[X])))
cand.append((cur2, (cur2[Y]+d, cur2[X])))
else: # 세로 방향 일 때
LEFT, RIGHT = -1, 1
for d in [LEFT, RIGHT]:
if new_board[cur1[Y]][cur1[X]+d] == 0 and new_board[cur2[Y]][cur2[X]+d] == 0:
cand.append(((cur1[Y], cur1[X]+d), cur1))
cand.append(((cur2[Y], cur2[X]+d), cur2))
return cand
def solution(board):
# board 외벽 둘러싸기
N = len(board)
new_board = [[1] * (N+2) for _ in range(N+2)]
for i in range(N):
for j in range(N):
new_board[i+1][j+1] = board[i][j]
# 현재 좌표 위치 큐 삽입, 확인용 set
que = deque([((1, 1), (1, 2), 0)])
confirm = set([((1, 1), (1, 2))])
while que:
cur1, cur2, count = que.popleft()
if cur1 == (N, N) or cur2 == (N, N):
return count
for nxt in can_move(cur1, cur2, new_board):
if nxt not in confirm:
que.append((*nxt, count+1))
confirm.add(nxt)
주의 :
이 문제는 좌표가 두개이고 회전처리가 까다워 난이도가 높은 편이다.
회전하는 경우를 가로방향일때와 세로방향일때가 나눠서 풀어주어야 한다.
항상 좋은 글 너무 감사합니다ㅠㅜ 파이썬 코드 보고 있는데 코드들이 진짜 너무 좋아요!