블록 이동하기 (Python)

https://programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

---

문제 해결을 위한 과정

이 문제의 경우 해결을 하기는 했는데 너무 복잡하게 해결해서 인터넷에서 간결한 코드를 찾다가 나동빈 님의 코드가 너무 간단명료하게 되어있고 set을 이용하는 저로서는 생각도 못해본 기발한 방법을 사용하셨기에 해당 코드를 아주 약간 변환해서 업로드합니다. 아직 멀었다는 것을 느끼며 포스팅합니다.

---

소스코드

from collections import deque
 
def can_move(pos, graph):
    next_pos = []
    pos = list(pos)
    lx, ly, rx, ry = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    for i in range(4):
        nlx, nly, nrx, nry = lx+dx[i], ly+dy[i], rx+dx[i], ry+dy[i]
        if graph[nlx][nly] == 0 and graph[nrx][nry] == 0:
            next_pos.append({(nlx, nly), (nrx, nry)})
    if lx == rx: # 가로인 경우
        for i in [-1, 1]:
            if graph[lx+i][ly] == 0 and graph[rx+i][ry] == 0:
                next_pos.append({(lx,ly), (lx+i, ly)})
                next_pos.append({(rx, ry), (rx+i, ry)})
    elif ly == ry: # 세로인 경우
        for i in [-1, 1]:
            if graph[lx][ly+i] == 0 and graph[rx][ry+i] == 0:
                next_pos.append({(lx, ly), (lx, ly+i)})
                next_pos.append({(rx, ry), (rx, ry+i)})
    return next_pos
 
def solution(board):
    n = len(board) + 2
    m = len(board)
    graph = [[1]*n for _ in range(n)]
    for i in range(m):
        for j in range(m):
            graph[i+1][j+1] = board[i][j]
    q = deque()
    visited = []
    pos = {(1, 1), (1, 2)}
    q.append((pos, 0))
    visited.append(pos)
    while q:
        pos, cost = q.popleft()
        if (m, m) in pos:
            return cost
        for next_pos in can_move(pos, graph):
            if next_pos not in visited:
                q.append((next_pos, cost+1))
                visited.append(next_pos)
    return 0