[프로그래머스][KAKAO_BLIND][2020] 블록 이동하기

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

from collections import deque, defaultdict

def set_rotate():
    dir = defaultdict()
    dir[(-1, 0)] = [(1,1,0,1), (1,-1,0,-1)]
    dir[(1,0)] = [(-1,1,0,1), (-1,-1,0,-1)]
    dir[(0,-1)] = [(-1,1,-1,0), (1,1,1,0)]
    dir[(0,1)] = [(1,-1,1, 0), (-1,-1,-1, 0)]
    return dir

def get_rotate_coord(x_r, x_c, y_r, y_c, N, dir, board):
    nw_list = []
    for d_r, d_c, z_r, z_c in dir[(x_r - y_r, x_c - y_c)]:
        nw_r, nw_c = x_r + d_r, x_c + d_c
        n_r, n_c = x_r + z_r, x_c + z_c
        if 0 <= nw_r < N and 0 <= nw_c < N and board[n_r][n_c] == 0 and board[nw_r][nw_c] == 0:
            nw_list.append((nw_r, nw_c))
    return nw_list

def get_dir_coord(x_r, x_c, y_r, y_c, N, dir, board):
    nw_list = []
    for d_r, d_c in dir:
        nw_x_r, nw_x_c, nw_y_r, nw_y_c = x_r + d_r, x_c + d_c, y_r + d_r, y_c + d_c
        if 0 <= nw_x_r < N and 0 <= nw_x_c < N and 0 <= nw_y_r < N and 0 <= nw_y_c < N and\
            board[nw_x_r][nw_x_c] == 0 and board[nw_y_r][nw_y_c] == 0:
            nw_list.append((nw_x_r, nw_x_c, nw_y_r, nw_y_c))
    return nw_list

def solution(board):
    N = len(board)
    visitied = defaultdict(bool)
    rotate = set_rotate()
    dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = deque([(0,0,0,1,0)])
    visitied[frozenset({(0,0),(0,1)})] = True

    while True:
        x_r, x_c, y_r, y_c, cost = q.popleft()
        if x_r == x_c == N-1 or y_r == y_c == N-1:
            return cost

        for nw_x_r, nw_x_c, nw_y_r, nw_y_c in get_dir_coord(x_r, x_c, y_r, y_c, N, dir, board):
            if not visitied[frozenset({(nw_x_r, nw_x_c), (nw_y_r, nw_y_c)})]:
                visitied[frozenset({(nw_x_r, nw_x_c), (nw_y_r, nw_y_c)})] = True
                q.append((nw_x_r, nw_x_c, nw_y_r, nw_y_c, cost+1))

        for nw_x_r, nw_x_c in get_rotate_coord(x_r, x_c, y_r, y_c, N, rotate, board):
            if not visitied[frozenset({(nw_x_r, nw_x_c), (y_r, y_c)})]:
                visitied[frozenset({(nw_x_r, nw_x_c), (y_r, y_c)})] = True
                q.append((nw_x_r, nw_x_c, y_r, y_c, cost + 1))
        for nw_y_r, nw_y_c in get_rotate_coord(y_r, y_c, x_r, x_c, N, rotate, board):
            if not visitied[frozenset({(x_r, x_c), (nw_y_r, nw_y_c)})]:
                visitied[frozenset({(x_r, x_c), (nw_y_r, nw_y_c)})] = True
                q.append((x_r, x_c, nw_y_r, nw_y_c, cost + 1))

• 좌표
  
  • 상태에 따른 이동할 위치와 조건을 dir/rotate에 저장
  • 이미 탐색한 위치를 frozenset의 set으로 저장
• 큐
  • 다음 이동 위치를 cost와 함께 저장
  • 최소 거리이므로 도착시 바로 종료

 

다른 사람이 작성한 코드

None

 

기억해야할 것

• 함수를 나눌 때 더 명료하게 나누면 좋겠다
  
  • 지금 지저분하게 긴 내용들을 더 함수화하여 깔끔하게 할 방법이 있을 듯 하다