문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/60063#
from collections import deque
dx,dy = [-1,1,0,0],[0,0,-1,1]
def canMove(board,cur1,cur2):
# 직선이동
arr = [] # 이동가능한 좌표 모음
for i in range(4):
nx1 = cur1[0] + dx[i]
ny1 = cur1[1] + dy[i]
nx2 = cur2[0] + dx[i]
ny2 = cur2[1] + dy[i]
if board[nx1][ny1] == 0 and board[nx2][ny2] == 0:
arr.append(((nx1,ny1), (nx2,ny2)))
# 회전이동
# 세로로 있는지 가로로 있는지 확인
if cur1[0] == cur2[0]: # 가로방향
up = -1
down = 1
for d in [up,down]:
if board[cur1[0]+d][cur1[1]] == 0 and board[cur2[0]+d][cur2[1]] ==0:
arr.append((cur1, (cur1[0]+d, cur1[1])))
arr.append((cur2, (cur2[0]+d, cur2[1])))
else: # 세로방향 일때
left = -1
right = 1
for d in [left,right]:
if board[cur1[0]][cur1[1]+d] == 0 and board[cur2[0]][cur2[1]+d] == 0:
arr.append(((cur1[0], cur1[1]+d), cur1))
arr.append(((cur2[0], cur2[1]+d), cur2))
return arr
def solution(board):
# 두개의 좌표로 visited 여부를 체크할때는 그냥 set안에서 존재하는 지 여부로 하자
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]
q = deque()
q.append(((1,1),(1,2),0))
confirm = set([((1,1),(1,2))])
while q:
cur1,cur2,cnt = q.popleft()
if cur1 == (n,n) or cur2 == (n,n):
return cnt
for next in canMove(new_board, cur1, cur2):
if next not in confirm:
q.append((next[0],next[1],cnt+1))
confirm.add(next)