[PRO] 블록 이동하기

N범위도 작고, 최단경로라 BFS로 하려 했는데, 조건이 까다로워 DFS로 갔다. 생각해보니 경로상 있는 조건이 아니어서 BFS로 하는게 나았을 것 같다.(회전, 일반이동 모두 가중치가 1이기도 하고)

그리고 BFS로 하면 visited배열도 신경안쓰고 처음 나타난게 정답이니 로직이 좀 더 간단해진다.

회전하는 부분 로직이 꽤 까다롭다.

import sys
sys.setrecursionlimit(10**6)

dx = [1,-1,0,0]
dy = [0,0,1,-1]

rot_dx = [1,1,-1,-1]
rot_dy = [-1,1,1,-1]

ans = float('inf')
global_board = None
N = None # global_board에서 가로,세로


def is_valid(x,y):
    if 0<=x<N and 0<=y<N and global_board[x][y]==0:
        return True
    return False


def direction_and_coord(x1,y1,x2,y2):
    if x1==x2:
        return 0, x1, min(y1,y2) # 방향과 기준 좌표
    return 1, min(x1,x2), y1 # 방향과 기준 좌표


def dfs(x_1,y_1,x_2,y_2, cnt, visited):
    if (x_1,y_1) == (N-1, N-1) or (x_2, y_2) == (N-1, N-1):
        ans = min(ans, cnt)
        return
    
    x_y_list = []
    for i in range(4): # 상하좌우
        new_x_1, new_y_1 = x_1 + dx[i], y_1 + dy[i]
        new_x_2, new_y_2 = x_2 + dx[i], y_2 + dy[i]
        x_y_list.append((new_x_1, new_y_1, new_x_2, new_y_2))
    
    for i in range(4):
        if rot_dx[i], rot_dy[i] == (-1,-1):
    
    
    for new_x_1, new_y_1, new_x_2, new_y_2 in x_y_list:
        dir, x, y = direction_and_coord(new_x_1, new_y_1, new_x_2, new_y_2)
        
        if is_valid(new_x_1, new_y_1) and is_valid(new_x_2, new_y_2) and not visited[dir][x][y]:
            print(new_x_1, new_y_1, new_x_2, new_y_2)
            visited[dir][x][y] = True
            dfs(new_x_1,new_y_1,new_x_2,new_y_2, cnt+1, visited)
            visited[dir][x][y] = False
        

def solution(board):
    global global_board, ans, N
    global_board = board
    N = len(global_board)
    x_1, y_1 = 0,0
    x_2, y_2 = 0,1
    visited = [[[False]*2 for _ in range(N)] for _ in range(N)] # 방문여부
    dfs(x_1, y_1, x_2, y_2, 0, visited)
    
    ans = 0 # 정답낼때 주석처리 필요
    return ans