블록 이동하기 Python 정리 및 구현 (카카오 기출 / 프로그래머스)

블록 이동하기

프로그래머스: https://school.programmers.co.kr/learn/courses/30/lessons/60063

Edge case

1. BFS 범위 설정

• <= N-1 하던가 < N 하던가 둘 중 하나만 해라

2. 최단경로 관련 문제에서 Visited

• 미리 기록되어있는건, 최단경로로 이미 지나간 곳이라고 생각해서

  • 중복으로 기록해도 됨

• 또한 확인할때 배열형태가 아닌 list형태로 좌표를 넣는것도 고려해볼만 해

  • 다만 때에 따라서 set을 이용해서 ((x1, y1), (x2, y2))와 ((x2, y2), (x1, y1))을 구별하지 않도록 설정하는게 좋음

---

Code

1. 1트 (FAIL)

Test case 1~3만 통과

• 여기서는 가로모드로 아래로 움직일 수 있따는 걸 고려하지 않음

# 블록 이동하기
# https://school.programmers.co.kr/learn/courses/30/lessons/60063
# 15:05 - 

# 좌하우상
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

ddx = [1, 1, -1, -1]
ddy = [1, -1, -1, 1]

INF = int(1e9)
min_cnt = INF
N = 0

def dfs(x, y, dir, cnt, check, board):  # @@ 여기서 변형한 값은 다시 원복이 필요함
    global min_cnt
    """
    @@ PARAM
    """
    # 같은 위치를 같은 방향으로 밟거나
        # 얘는 INF을 리턴하고 종료
    # 최종위치에 도달하면 종료
        # cnt를 return하고
    if x == (N-1) and y == (N-1):
        min_cnt = min(min_cnt, cnt)
        return
    if x+dx[dir] == (N-1) and y+dy[dir] == (N-1):
        min_cnt = min(min_cnt, cnt)
        return

    # 직진
    nx, ny = x+dx[dir], y+dy[dir]
    nnx, nny = nx+dx[dir], ny+dy[dir]
    if not (nnx < 0 or nnx >= N or nny < 0 or nny >= N):
        if check[nx][ny] == 0:
            if not (board[nx][ny] or board[nnx][nny]):
                check[nx][ny] = 1   # 넘어가자마자 바로 체크에 걸려버림
                dfs(nx, ny, dir, cnt+1, check, board)
                check[nx][ny] = 0
        
    # 후진
    nx, ny = x+dx[(dir+2) % 4], y+dy[(dir+2) % 4]   # @@ % 꼭 해줘야해
    if not (nx < 0 or nx >= N or ny < 0 or ny >= N):
        if check[nx][ny] == 0:
            if not board[nx][ny]:
                check[nx][ny] = 1
                dfs(nx, ny, dir, cnt+1, check, board)   # 후진은 방향변경은 아냐!
                check[nx][ny] = 0

    # 시계 방향
    nx, ny = x+dx[(dir+1) % 4], y+dy[(dir+1) % 4]
    if not (nx < 0 or nx >= N or ny < 0 or ny >= N):
        if not board[x+ddx[dir]][y+ddy[dir]]:   # 회전방향에 물체가 있으면 안됨
            if not board[nx][ny]:
                if check[x][y] != 2:
                    check[x][y] = 2
                    dfs(x, y, (dir+1) % 4, cnt+1, check, board) # 얘는 그냥 (x, y)임 (nx, ny)아님!
                    check[x][y] = 0
    
    
    # 반시계 방향
    nx, ny = x+dx[(dir-1) % 4], y+dy[(dir-1) % 4]
    if not (nx < 0 or nx >= N or ny < 0 or ny >= N):
        if not board[x+ddx[(dir-1) % 4]][y+ddy[(dir-1) % 4]]:   # 회전방향에 물체가 있으면 안됨
            if not board[nx][ny]:   # 장애물도 있으면 안됨
                if check[x][y] != 2:
                    check[x][y] = 2
                    dfs(x, y, (dir-1) % 4, cnt+1, check, board)
                    check[x][y] = 0


    # 옆칸에서 회전
    x, y = x+dx[dir], y+dy[dir]
    dir = (dir - 2) % 4
    # 시계
    nx, ny = x+dx[(dir+1) % 4], y+dy[(dir+1) % 4]
    if not (nx < 0 or nx >= N or ny < 0 or ny >= N):
        if not board[x+ddx[dir]][y+ddy[dir]]:   # 회전방향에 물체가 있으면 안됨
            if not board[nx][ny]:
                if check[x][y] != 2:
                    check[x][y] = 2
                    dfs(x, y, (dir+1) % 4, cnt+1, check, board) # 얘는 그냥 (x, y)임 (nx, ny)아님!
                    check[x][y] = 0

    # 반시계
    nx, ny = x+dx[(dir-1) % 4], y+dy[(dir-1) % 4]
    if not (nx < 0 or nx >= N or ny < 0 or ny >= N):
        if not board[x+ddx[(dir-1) % 4]][y+ddy[(dir-1) % 4]]:   # 회전방향에 물체가 있으면 안됨
            if not board[nx][ny]:   # 장애물도 있으면 안됨
                if check[x][y] != 2:
                    check[x][y] = 2
                    dfs(x, y, (dir-1) % 4, cnt+1, check, board)
                    check[x][y] = 0

def solution(board):
    global N
    N = len(board)
    check = [[0] * N for _ in range(N)]
    check[0][0] = 1
    dfs(0, 0, 0, 0, check, board)

board = [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]]
solution(board)
print(min_cnt)

---

2. 2트 (FAIL)

Test case 1~3만 통과

• 모든 이동 경우의 수를 고려하였으나, check 배열도 queue에 넣는바람에 시간 초과

# 블록 이동하기
# https://school.programmers.co.kr/learn/courses/30/lessons/60063

from collections import deque
from copy import deepcopy

# 오, 왼, 하, 상
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

min_cost = int(1e9)
N = 0
def get_next_pos(board, pos):
    cand = list()

    x1, y1, x2, y2 = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
    for dir in range(4):
        nx1, ny1, nx2, ny2 = x1+dx[dir], y1+dy[dir], x2+dx[dir], y2+dy[dir]
        if nx1 < 0 or nx1 >= N or ny1 < 0 or ny1 >= N:
            continue
        if nx2 < 0 or nx2 >= N or ny2 < 0 or ny2 >= N:
            continue
        if board[nx1][ny1] or board[nx2][ny2]:
            continue
        cand.append(((nx1, ny1), (nx2, ny2)))


    for rot in range(2):
        if y1 == y2:    # 세로일때
            # 기준점을 위로 잡을까 밑으로 잡을까
            ny1, ny2 = y1+dy[rot], y2+dy[rot]   # 처음엔 오른쪽 영역 먼저 확인할거임
            if not (ny1 < 0 or ny1 >= N or ny2 < 0 or ny2 >= N):    # @@ N-1이라고 써놓음
                if not (board[x1][ny1] or board[x2][ny2]):
                    cand.append(((x1, y1), (x1, ny2)))
                    cand.append(((x2, ny1), (x2, y2)))

        elif x1 == x2:
            rot += 2   # 하 부터 보는거임
            nx1, nx2 = x1+dx[rot], x2+dx[rot]
            if not (nx1 < 0 or nx1 >= N or nx2 < 0 or nx2 >= N):
                if not (board[nx1][y1] or board[nx2][y2]):
                    cand.append(((x1, y1), (nx2, y1)))
                    cand.append(((nx1, y2), (x2, y2)))

    return list(set(cand))      # @@ set으로 변환하기 위해 list를 tuple형태로 변환함

def solution(board):
    global min_cost
    global N

    N = len(board)
    
    q = deque()

    check = [[0]*N for _ in range(N)]
    check[0][0], check[0][1] = 1, 1
    
    pos = [(0, 0), (0, 1)]  # 현재 위치
    
    q.append((pos, check, 0))

    while q:
        pos, check, cost = q.popleft()
        # 이걸 어째 종료조건을 추가하지 않을 수 없잖아?
        if (pos[0][0], pos[0][1]) == (N-1, N-1) or (pos[1][0], pos[1][1]) == (N-1, N-1):
            min_cost = min(min_cost, cost)

        for cand in get_next_pos(board, pos):
            if check[cand[0][0]][cand[0][1]] and check[cand[1][0]][cand[1][1]]:
                continue
            check2 = deepcopy(check)    # @@ 여기서 deepcopy안하면 ~for cand in get ...~ 이 구간이 모두 같은 check를 공유하게됨
            check2[cand[0][0]][cand[0][1]], check2[cand[1][0]][cand[1][1]] = 1, 1
            q.append((cand, check2, cost+1))

    print(min_cost)

solution([[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]])

---

3. 3트

성공

• set을 이용하여, ((x1, y1), (x2, y2))와 ((x2, y2), (x1, y1))을 구별하지 않아서 훨씬 빠르게 검증 가능

• check list 기록이 누적되는게 문제가 될거처럼 보이지만

  • 사실은 최단거리순으로 들리기 때문에, 미리 체크되어있는곳은 사실상 최단경로로 도달한 경험이 있는 지역임

# 블록 이동하기
# https://school.programmers.co.kr/learn/courses/30/lessons/60063

from collections import deque

# 오, 왼, 하, 상
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

N = 0

def get_next_pos(board, pos):
    cand = list()

    ((x1, y1), (x2, y2)) = pos
    
    for dir in range(4):
        nx1, ny1, nx2, ny2 = x1+dx[dir], y1+dy[dir], x2+dx[dir], y2+dy[dir]
        if nx1 < 0 or nx1 >= N or ny1 < 0 or ny1 >= N:
            continue
        if nx2 < 0 or nx2 >= N or ny2 < 0 or ny2 >= N:
            continue
        if board[nx1][ny1] or board[nx2][ny2]:
            continue
        cand.append(set(((nx1, ny1), (nx2, ny2))))


    for rot in range(2):
        if y1 == y2:    # 세로일때
            # 기준점을 위로 잡을까 밑으로 잡을까
            ny1, ny2 = y1+dy[rot], y2+dy[rot]   # 처음엔 오른쪽 영역 먼저 확인할거임
            if not (ny1 < 0 or ny1 >= N or ny2 < 0 or ny2 >= N):    # @@ N-1이라고 써놓음
                if not (board[x1][ny1] or board[x2][ny2]):
                    cand.append(set(((x1, y1), (x1, ny2))))
                    cand.append(set(((x2, ny1), (x2, y2))))

        elif x1 == x2:
            rot += 2   # 하 부터 보는거임
            nx1, nx2 = x1+dx[rot], x2+dx[rot]
            if not (nx1 < 0 or nx1 >= N or nx2 < 0 or nx2 >= N):
                if not (board[nx1][y1] or board[nx2][y2]):
                    cand.append(set(((x1, y1), (nx2, y1))))
                    cand.append(set(((nx1, y2), (x2, y2)))) # @@@ set으로 넣어놓으면 if .. in 연산할때 ((x1, y1), (x2, y2))냐  ((x2, y2), (x1, y1))이냐 구분하지않음

    return cand      # @@ set으로 변환하기 위해 list를 tuple형태로 변환함

def solution(board):
    global N
    N = len(board)
    
    q = deque()

    pos = ((0, 0), (0, 1))  # 현재 위치
    check = list()
    check.append(pos)
    
    q.append((pos, 0))

    while q:
        pos, cost = q.popleft()

        if (N-1, N-1) in pos:
            return cost

        for cand in get_next_pos(board, pos):
            if cand in check: 
                continue
            check.append(cand)	# @@@@
            q.append((cand, cost+1))