프로그래머스 - 블록이동하기 - 구현
문제
입력
나의 처음 코드
움직이 있을 때마다, 두개의 날개중에 하나로 기준을 잡고 회전하는 것과 상하좌우로 움직이는 것을 고려해야 한다. 단, 아래 사진에도 나와있듯이 각 날개의 좌표가 x나 y가 같을 때는 따라오는 규칙들이 존재한다.
풀이 사진
def bfs(left, right, board):
N = len(board)
visit_dict = {(left, right): 1}
queue = [(left, right, 0)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
while queue:
tmp_queue = []
for ((l_x, l_y), (r_x, r_y), cnt) in queue:
if (l_x, l_y) == (N - 1, N - 1) or (r_x, r_y) == (N - 1, N - 1):
return cnt
for i in range(4):
nl_x, nl_y = l_x + dx[i], l_y + dy[i]
nr_x, nr_y = r_x + dx[i], r_y + dy[i]
if l_x == r_x:
if 0 <= nl_x < N and 0 <= nl_y < N and 0 <= nr_x < N and 0 <= nr_y < N:
if board[nl_x][nl_y] == 0 and board[nr_x][nr_y] == 0:
if i == 1:
if ((l_x, l_y), (l_x + 1,
l_y)) not in visit_dict:
visit_dict[((l_x, l_y), (l_x + 1,
l_y))] = 1
tmp_queue.append(
((l_x, l_y), (l_x + 1, l_y), cnt + 1))
if ((r_x + 1, r_y), (r_x,
r_y)) not in visit_dict:
visit_dict[((r_x + 1, r_y), (r_x,
r_y))] = 1
tmp_queue.append(
((r_x + 1, r_y), (r_x, r_y), cnt + 1))
elif i == 3:
if ((l_x, l_y), (l_x - 1,
l_y)) not in visit_dict:
visit_dict[((l_x, l_y), (l_x - 1,
l_y))] = 1
tmp_queue.append(
((l_x, l_y), (l_x - 1, l_y), cnt + 1))
if ((r_x - 1, r_y), (r_x,
r_y)) not in visit_dict:
visit_dict[((r_x - 1, r_y), (r_x,
r_y))] = 1
tmp_queue.append(
((r_x - 1, r_y), (r_x, r_y), cnt + 1))
if ((nl_x, nl_y), (nr_x, nr_y)) not in visit_dict:
visit_dict[((nl_x, nl_y), (nr_x, nr_y))] = 1
tmp_queue.append(
((nl_x, nl_y), (nr_x, nr_y), cnt + 1))
else:
if 0 <= nl_x < N and 0 <= nl_y < N and 0 <= nr_x < N and 0 <= nr_y < N:
if board[nl_x][nl_y] == 0 and board[nr_x][nr_y] == 0:
if i == 0:
if ((l_x, l_y), (l_x,
l_y + 1)) not in visit_dict:
visit_dict[((l_x, l_y), (l_x,
l_y + 1))] = 1
tmp_queue.append(
((l_x, l_y), (l_x, l_y + 1), cnt + 1))
if ((r_x, r_y + 1), (r_x,
r_y)) not in visit_dict:
visit_dict[((r_x, r_y + 1), (r_x,
r_y))] = 1
tmp_queue.append(
((r_x, r_y + 1), (r_x, r_y), cnt + 1))
elif i == 2:
if ((l_x, l_y), (l_x,
l_y - 1)) not in visit_dict:
visit_dict[((l_x, l_y), (l_x,
l_y - 1))] = 1
tmp_queue.append(
((l_x, l_y), (l_x, l_y - 1), cnt + 1))
if ((r_x, r_y - 1), (r_x,
r_y)) not in visit_dict:
visit_dict[((r_x, r_y - 1), (r_x,
r_y))] = 1
tmp_queue.append(
((r_x, r_y - 1), (r_x, r_y), cnt + 1))
if ((nl_x, nl_y), (nr_x, nr_y)) not in visit_dict:
visit_dict[((nl_x, nl_y), (nr_x, nr_y))] = 1
tmp_queue.append(
((nl_x, nl_y), (nr_x, nr_y), cnt + 1))
queue = tmp_queue
return 0
def solution(board):
return bfs((0, 0), (0, 1), board)
코드의 모듈화를 하지 않아서 많이 복잡해 보이지만, 결국에는 위의 설명과 마찬가지로 매번 움직이고 좌표를 확인하는 것만 반복하면 된다. 목적지에 도달하지 않는 경우는 없다고 하였기 떄문에, 더욱 쉽게 풀 수 있을 것이다.