[programmers] 블록 이동하기_BFS
Date:
블럭 이동하기
내 풀이
- 방식 : BFS
- visited 구성하는 방법에서 오래 걸렸음
- 방문하는 방법을 모두 visited에 담아서 거쳐간 곳인지 확인하는 방식으로 풀이
- map 사이즈가 100이하로 작기 때문에 가능한 것 같음
📰code
from collections import deque
def solution(board):
w,h = len(board[0]),len(board)
visited = []
x1,y1,x2,y2 = 0,0,0,1
m = 0
visited.append((x1,y1,x2,y2))
q = deque()
q.append((x1,y1,x2,y2,m))
while q:
x1,y1,x2,y2,m = q.popleft()
if (x1==h-1 and y1 == w-1) or (x2==h-1 and y2 == w-1): return m
move = [(0,-1),(0,1),(-1,0),(1,0)]
if x1 == x2 :
rotate = [(-1,0),(1,0)]
else :
rotate = [(0,-1),(0,1)]
for dx,dy in move: # 긴 방향으로 이동
mx1,my1,mx2,my2 = x1-dx,y1-dy,x2-dx,y2-dy
if 0<=mx1<h and 0<=my1<w and 0<=mx2<h and 0<=my2<w :
if board[mx1][my1] == 0 and board[mx2][my2] == 0:
if (min(mx1,mx2),min(my1,my2),max(mx1,mx2),max(my1,my2)) not in visited:
q.append((mx1,my1,mx2,my2,m+1))
visited.append((min(mx1,mx2),min(my1,my2),max(mx1,mx2),max(my1,my2)))
for rx,ry in rotate:
rx1,ry1,rx2,ry2 = x1-rx,y1-ry,x2-rx,y2-ry
if 0<=rx1<h and 0<=ry1<w and 0<=rx2<h and 0<=ry2<w : # 넓은 방향으로 이동
if board[rx1][ry1] == 0 and board[rx2][ry2] == 0: # 이동 가능하고
if (min(x1,rx1),min(y1,ry1),max(x1,rx1),max(y1,ry1)) not in visited:
q.append((rx1,ry1,x1,y1,m+1))
visited.append((min(x1,rx1),min(y1,ry1),max(x1,rx1),max(y1,ry1)))
if (min(x2,rx2),min(y2,ry2),max(x2,rx2),max(y2,ry2)) not in visited:
q.append((x2,y2,rx2,ry2,m+1))
visited.append((min(x2,rx2),min(y2,ry2),max(x2,rx2),max(y2,ry2)))
틀렸던 풀이
Test Case : 더 빠른 시기에 방문 했지만, 더 이상 진행이 안된 경우가 안풀림
board = [[0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
answer = 18
📰code
from collections import deque
def solution(board):
w,h = len(board[0]),len(board)
visited = [[1e9 for _ in range(len(board[0]))] for _ in range(len(board))]
x1,y1,x2,y2 = 0,0,0,1
m = 0
visited[x1][y1]=-1
visited[x2][y2]=-1
q = deque()
q.append((x1,y1,x2,y2,m))
while q:
x1,y1,x2,y2,m = q.popleft()
if (x1==h-1 and y1 == w-1) or (x2==h-1 and y2 == w-1): return m
if x1 == x2 :
move = [(0,-1),(0,1)]
rotate = [(-1,0),(1,0)]
else :
move = [(-1,0),(1,0)]
rotate = [(0,-1),(0,1)]
for dx,dy in move: # 긴 방향으로 이동
mx1,my1,mx2,my2 = x1-dx,y1-dy,x2-dx,y2-dy
if 0<=mx1<h and 0<=my1<w and 0<=mx2<h and 0<=my2<w :
if board[mx1][my1] == 0 and board[mx2][my2] == 0:
if visited[mx1][my1] > m or visited[mx2][my2] > m:
visited[mx1][my1] = m
visited[mx2][my2] = m
q.append((mx1,my1,mx2,my2,m+1))
for rx,ry in rotate:
rx1,ry1,rx2,ry2 = x1-rx,y1-ry,x2-rx,y2-ry
if 0<=rx1<h and 0<=ry1<w and 0<=rx2<h and 0<=ry2<w : # 넓은 방향으로 이동
if board[rx1][ry1] == 0 and board[rx2][ry2] == 0: # 이동 가능하고
if visited[rx1][ry1] > m or visited[rx2][ry2] > m :
q.append((rx1,ry1,rx2,ry2,m+1))
if visited[rx1][ry1] > m : q.append((rx1,ry1,x1,y1,m+1))
if visited[rx2][ry2] > m : q.append((x2,y2,rx2,ry2,m+1))
visited[rx1][ry1] = m
visited[rx2][ry2] = m
💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡
댓글