## 보드의 벽으로 1 둘러싸기. 코딩 편하게하려면 그래야할듯?
## 현재시간 카운트 => cnt
## 로봇의 현재위치 => 인덱스 : [[ly,lx], [ry,rx]]
# 로봇의 이동경로 => 보드에 -1로 표현. 1로 하면 안돼나? 회전 가능한데 막을수도 있으니까
# => 이동경로를 이렇게 하기보다...로봇의 현재위치 좌표를 set으로 저장해두자. 가능한 모든 이동 후보군을 set에 넣으면 됨
# 로봇의 목적지 => 인덱스 : [len(board), len(board)]
# 로봇의 이동 => BFS 노드 확장
# 지금까지중 로봇의 최소 이동경로 => BFS
# 노드에 담길 정보는 현재위치, 이동경로표시된 보드, 카운트
# "노드" 라는걸 쓰지않음...큐에 그냥 넣게됨 큐에는 뭘넣느냐..cur1, cur2, cnt
# 1. 현재 위치와 목표지점 비교. 도달시 카운트 리턴, 실패시 2로
# 2. 두개의 노드 확장... => 이부분 잘못생각한듯? 이동했다 빽해서 회전으로 가는게 맞지않을까?? 컴터 동시에 뭐 못하잖아. 그럼 이동부터 하다가 더이상 이동 못할때 회전하는거로 할까? 그러다 회전하다가 더이상 회전못하는곳 만나면? 그때 빽을 하면 되려나
# 2.1 지금까지의 경로 확인. 상하좌우 순서로 이동가능한곳 탐색후 가능하면 이동
# 2.2 (이동성공)로봇의 현재위치 갱신, 현재위치 정보 토대로 로봇의 이동경로 갱신, 카운트 증가, 1로 돌아감
# 2.3 (이동실패)상,하,좌,우 모두 갈수있는 곳이 없거나 이미 가본 지점인 경우 그노드는 끝..더이상 확장 불가
# 3. 회전의 경우
# 3.1 지금까지의 경로 확인. 오른쪽축 중심으로 위 아래 회전, 왼쪽축 중심으로 위 아래 외전 가능한곳 탐색후 가능하면 이동
# 3.2 (회전성공)로봇의 현재위치 갱신, 현재위치 정보 토대로 로봇의 이동경로 갱신, 카운트 증가, 1로 돌아감
# 3.3 (회전실패)회전할수있는곳이 없거나 이미 가본 지점인 경우 그 노드는끝 # 새로 정리..
# 보드는 1로 감싸줌
# 현재위치는 좌표 두개로 표현
# 두 좌표의 y값이 일치하면 가로인상태, x값이 일치하면 세로인 상태
# 경로는 좌표를 set으로 넣어줘서 not in 으로 체크해주기
# 시간카운트는 따로 큐에 넣어주기..?이유가있나 아...정답을 리턴할때 필요하겠다
# 이동가능한 모든 좌표들의 리스트 뽑아주고, 리턴된 리스트의 좌표들이 경로set에 없다면 큐에 저장! 있는건 무시
# popleft()로 젤 앞에있는거 빼서 같은 작업을 반복해줌
from collections import deque
def can_move(cur1, cur2, new_board):
# 가능한 후보 이동군을 만들어서 리스트에 저장해주고 리턴해주면됨
cand = []
# 상(1,0)하(-1,0)좌(0,-1)우(0,1)
DIRECTIONS = [(1,0), (-1,0), (0,-1), (0,1)]
for dy, dx in DIRECTIONS:
nxt1 = (cur1[0] + dy, cur1[1] + dx)
nxt2 = (cur2[0] + dy, cur2[1] + dx)
if new_board[nxt1[0]][nxt1[1]] == 0 and new_board[nxt2[0]][nxt2[1]] == 0:
cand.append((nxt1,nxt2)) # cand.append([nxt1,nxt2])는?
if cur1[0] == cur2[0]: # 가로면
UP, DOWN = -1, 1
for d in [UP, DOWN]:
if new_board[cur1[0]+d][cur1[1]] == 0 and new_board[cur2[0]+d][cur2[1]] == 0:
cand.append((cur1, (cur1[0]+d, cur1[1])))
cand.append((cur2, (cur2[0]+d, cur2[1])))
else:
LEFT, RIGHT = -1, 1
for d in [LEFT, RIGHT]:
if new_board[cur1[0]][cur1[1]+d] == 0 and new_board[cur2[0]][cur2[1]+d] == 0:
cand.append(((cur1[0], cur1[1]+d), cur1))
cand.append(((cur2[0], cur2[1]+d), cur2))
return cand
def solution(board):
# 보드를 1로 감싸줌
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, cnt = que.popleft()
if cur1 == (N, N) or cur2 == (N, N):
return cnt
for nxt in can_move(cur1, cur2, new_board):
if nxt not in confirm:
que.append((*nxt, cnt+1)) # 왜 *?
confirm.add(nxt)
삽질하는 개발자 지망생