title: "[프로그래머스] 블록 이동하기 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/60063"
description: "프로그래머스 Level 3 문제 [블록 이동하기]의 풀이를 정리합니다."
from queue import deque
N = -1
A = None
def is_valid(r1, c1, r2=None, c2=None):
if r2 is not None and c2 is not None:
tmp = (0 <= r1 < N) and (0 <= c1 < N) and (0 <= r2 < N) and (0 <= c2 < N)
return tmp and A[r1][c1] == 0 and A[r2][c2] == 0
else:
return (0 <= r1 < N) and (0 <= c1 < N) and A[r1][c1] == 0
def solution(board):
global N, A
N = len(board)
A = board
# 복잡해 보이지만, 상하좌우 이동 4가지,
# 왼쪽/오른쪽 혹은 위쪽/아래쪽 축으로 시계/반시계 회전 4가지 총 8가지
# 움직임이 있는 bfs로 해결해봅니다.
q, vis = deque(), set()
# (d, r1, c1, r2, c2)를 큐에 넣습니다.
# 항상 r1 <= r2, c1 <= c2가 되도록 합니다.
q.append( (0, 0, 0, 0, 1) )
vis.add( (0, 0, 0, 1) )
while q:
d, r1, c1, r2, c2 = q.popleft()
# 목적지에 도달했으면 이동 거리를 리턴합니다.
if r2 == N-1 and c2 == N-1:
return d
# 평행이동
# r1, c1, r1, c2의 대소 관계가 보존됩니다.
moves = [
# dr1, dc1, dr2, dc2
(0, 1, 0, 1), # 오른쪽
(0, -1, 0, -1), # 왼쪽
(-1, 0, -1, 0), # 위쪽
(1, 0, 1, 0), # 아래쪽
]
for dr1, dc1, dr2, dc2 in moves:
state = (r1+dr1, c1+dc1, r2+dr2, c2+dc2)
if is_valid(*state) and state not in vis:
q.append( (d+1, *state) )
vis.add(state)
# 회전
# 1. 가로로 놓여있는 경우
if r1 == r2:
# 1-1. 왼쪽 축, 반시계방향 회전
state = (r2-1, c2-1, r1, c1)
if is_valid(*state) and state not in vis and is_valid(r2-1, c2):
q.append( (d+1, *state) )
vis.add(state)
# 1-2. 왼쪽 축, 시계방향 회전
state = (r1, c1, r2+1, c2-1)
if is_valid(*state) and state not in vis and is_valid(r2+1, c2):
q.append( (d+1, *state) )
vis.add(state)
# 1-3. 오른쪽 축, 시계방향 회전
state = (r1-1, c1+1, r2, c2)
if is_valid(*state) and state not in vis and is_valid(r1-1, c1):
q.append( (d+1, *state) )
vis.add(state)
# 1-4. 오른쪽 축, 반시계방향 회전
state = (r2, c2, r1+1, c1+1)
if is_valid(*state) and state not in vis and is_valid(r1+1, c1):
q.append( (d+1, *state) )
vis.add(state)
# 2. 세로로 놓인 경우
else:
# 2-1. 위쪽 축, 시계방향 회전
state = (r2-1, c2-1, r1, c1)
if is_valid(*state) and state not in vis and is_valid(r1+1, c1-1):
q.append( (d+1, *state) )
vis.add(state)
# 2-2. 위쪽 축, 반시계방향 회전
state = (r1, c1, r2-1, c2+1)
if is_valid(*state) and state not in vis and is_valid(r1+1, c1+1):
q.append( (d+1, *state) )
vis.add(state)
# 2-3. 아래쪽 축, 시계방향 회전
state = (r2, c2, r1+1, c1+1)
if is_valid(*state) and state not in vis and is_valid(r2-1, c2+1):
q.append( (d+1, *state) )
vis.add(state)
# 2-4. 아래쪽 축, 반시계방향 회전
state = (r1+1, c1-1, r2, c2)
if is_valid(*state) and state not in vis and is_valid(r2-1, c2-1):
q.append( (d+1, *state) )
vis.add(state)
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges