블록 이동하기

블록 이동하기
2020 KAKAO BLIND RECRUITMENT 
759명 완료

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

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

경주로 건설과 거의 비슷한 문제인데.. 
같은 방식으로 코딩하려고 해보니 꽤 복잡하다.. 

https://comdoc.tistory.com/entry/%EA%B2%BD%EC%A3%BC%EB%A1%9C-%EA%B1%B4%EC%84%A4

경주로 건설에는 깊이우선검색에 메모이제이션과 가지치기를 병행해서 풀었는데..
(의도한 건 아니고 시뮬레이션과 생각의 흐름에 따라 코딩하다 보니...)

너비 우선 탐색을 이용해야 될 것 같다.. 

def solution(board):
    from collections import deque
    que = deque([(1, 1, 2, 1, 0)])
    visited = set()
    size = len(board)
    board = [[1 if i in (0, size + 1) or j in (0, size + 1) else board[i - 1][j - 1]
              for j in range(size + 2)] for i in range(size + 2)]
    while que:
        x1, y1, x2, y2, distance = que.popleft()
        if (x1, y1) == (size, size) or (x2, y2) == (size, size):
            return distance
        if (x1, y1, x2, y2) not in visited:
            visited.add((x1, y1, x2, y2))
            que.extend(find_next(x1, y1, x2, y2, distance + 1, board))


def find_next(x1, y1, x2, y2, distance, board):
    next_xy = []
    for move_x, move_y in ((1, 0), (0, 1), (-1, 0), (0, -1)):  # 전후좌우
        (nx1, ny1, nx2, ny2) = (x1 + move_x, y1 + move_y, x2 + move_x, y2 + move_y)
        if board[ny1][nx1] == 0 and board[ny2][nx2] == 0:
            next_xy.append((nx1, ny1, nx2, ny2, distance))
    if y1 == y2:  # 가로
        if board[y1 + 1][x1] == 0 and board[y1 + 1][x1 + 1] == 0:
            next_xy.append((x1, y1, x1, y1 + 1, distance))
            next_xy.append((x1 + 1, y1, x1 + 1, y1 + 1, distance))
        if board[y1 - 1][x1] == 0 and board[y1 - 1][x1 + 1] == 0:
            next_xy.append((x1, y1 - 1, x1, y1, distance))
            next_xy.append((x1 + 1, y1 - 1, x2, y1, distance))
    else:  # x1 == x2
        if board[y1][x1 + 1] == 0 and board[y1 + 1][x1 + 1] == 0:
            next_xy.append((x1, y1, x1 + 1, y2 - 1, distance))
            next_xy.append((x2, y2, x1 + 1, y1 + 1, distance))
        if board[y1][x1 - 1] == 0 and board[y1 + 1][x1 - 1] == 0:
            next_xy.append((x1 - 1, y1, x1, y2 - 1, distance))
            next_xy.append((x1 - 1, y1 + 1, x1, y2, distance))
    return next_xy

테스트 1 〉	통과 (0.13ms, 9.64MB)
테스트 2 〉	통과 (0.14ms, 9.89MB)
테스트 3 〉	통과 (0.12ms, 9.89MB)
테스트 4 〉	통과 (0.54ms, 9.76MB)
테스트 5 〉	통과 (0.39ms, 9.68MB)
테스트 6 〉	통과 (0.69ms, 9.93MB)
테스트 7 〉	통과 (1.58ms, 9.73MB)
테스트 8 〉	통과 (2.04ms, 9.82MB)
테스트 9 〉	통과 (2.02ms, 9.88MB)
테스트 10 〉	통과 (1.97ms, 9.89MB)
테스트 11 〉	통과 (1.31ms, 9.74MB)
테스트 12 〉	통과 (1.50ms, 9.75MB)
테스트 13 〉	통과 (26.31ms, 10.7MB)
테스트 14 〉	통과 (18.61ms, 10.2MB)

보기는 간단해 보여도 한땀 한땀.. ㅠ,.ㅠ