코딩 테스트(Python) [PCCP 기출문제] 4번 / 수레 움직이기

문제 설명

n x m 크기 격자 모양의 퍼즐판이 주어집니다.

퍼즐판에는 빨간색 수레와 파란색 수레가 하나씩 존재합니다. 각 수레들은 자신의 시작 칸에서부터 자신의 도착 칸까지 이동해야 합니다.

모든 수레들을 각자의 도착 칸으로 이동시키면 퍼즐을 풀 수 있습니다.

당신은 각 턴마다 반드시 모든 수레를 상하좌우로 인접한 칸 중 한 칸으로 움직여야 합니다. 단, 수레를 움직일 때는 아래와 같은 규칙이 있습니다.

• 수레는 벽이나 격자 판 밖으로 움직일 수 없습니다.
• 수레는 자신이 방문했던 칸으로 움직일 수 없습니다.
• 자신의 도착 칸에 위치한 수레는 움직이지 않습니다. 계속 해당 칸에 고정해 놓아야 합니다.
• 동시에 두 수레를 같은 칸으로 움직일 수 없습니다.
• 수레끼리 자리를 바꾸며 움직일 수 없습니다.

예를 들어, 아래 그림처럼 n = 3, m = 2인 퍼즐판이 있습니다.

• 속이 빨간색인 원은 빨간색 수레를 나타냅니다.
• 속이 파란색인 원은 파란색 수레를 나타냅니다.
• 테두리가 빨간색인 원은 빨간색 수레의 도착 칸을 나타냅니다.
• 테두리가 파란색인 원은 파란색 수레의 도착 칸을 나타냅니다.

위 퍼즐판은 아래와 같은 순서로 3턴만에 풀 수 있습니다.

 

 

• 빨간색 사선이 처진 칸은 빨간색 수레가 방문했던 칸을 나타냅니다. 규칙에 따라 빨간색 수레는 빨간색 사선이 처진 칸(방문했던 칸)으로는 이동할 수 없습니다.
• 파란색 사선이 처진 칸은 파란색 수레가 방문했던 칸을 나타냅니다. 규칙에 따라 파란색 수레는 파란색 사선이 처진 칸(방문했던 칸)으로는 이동할 수 없습니다.

• 위처럼 동시에 수레를 같은 칸으로 움직일 수는 없습니다.

퍼즐판의 정보를 나타내는 2차원 정수 배열 maze가 매개변수로 주어집니다. 퍼즐을 푸는데 필요한 턴의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 퍼즐을 풀 수 없는 경우 0을 return 해주세요.

 

from collections import deque
import copy

# 좌표가 미로 범위 내에 있는지 확인하는 함수
def is_bounded(x, m, n):
    return 0 <= x[0] < n and 0 <= x[1] < m

# 좌표가 벽(값이 5)인지 확인하는 함수
def is_wall(x, map):
    return map[x[0]][x[1]] == 5

# 두 좌표가 동일한 위치에 있는지 확인하는 함수 (충돌 여부 확인)
def is_crashed(x, y):
    return (x[0] == y[0]) and (x[1] == y[1])

# 좌표가 이미 방문된 위치인지 확인하는 함수
def is_visited(x, v):
    return v[x[0]][x[1]]

# 두 개의 경로가 서로 교차했는지 확인하는 함수
def is_crossed(a, b, c, d):
    return (a[0], a[1]) == (b[0], b[1]) and (c[0], c[1]) == (d[0], d[1])

def solution(maze):
    n = len(maze)  # 미로의 행 크기
    m = len(maze[0])  # 미로의 열 크기

    # 빨간 공과 파란 공의 초기 위치 찾기
    for i in range(n):
        for j in range(m):
            if maze[i][j] == 1:  # 빨간 공의 위치
                red = [i, j]
            elif maze[i][j] == 2:  # 파란 공의 위치
                blue = [i, j]

    # 방문 여부를 저장하는 배열 초기화
    vr_ = [[False for i in range(m)] for i in range(n)]  # 빨간 공 방문 여부
    vb_ = [[False for i in range(m)] for i in range(n)]  # 파란 공 방문 여부

    red_reached = False  # 빨간 공이 목표 지점에 도달했는지 확인
    blue_reached = False  # 파란 공이 목표 지점에 도달했는지 확인

    # BFS를 위한 큐 초기화 (현재 상태 저장)
    path = deque()
    path.append([red[0], red[1], blue[0], blue[1], vr_, vb_, 0])

    # 이동 방향 (상, 하, 좌, 우)
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    while path:
        # 현재 상태를 큐에서 꺼내옴
        rr, rc, br, bc, vr_temp, vb_temp, count = path.popleft()
        vr = copy.deepcopy(vr_temp)  # 빨간 공 방문 배열 복사
        vb = copy.deepcopy(vb_temp)  # 파란 공 방문 배열 복사
        vr[rr][rc] = True  # 현재 빨간 공 위치 방문 처리
        vb[br][bc] = True  # 현재 파란 공 위치 방문 처리

        # 빨간 공과 파란 공이 각각 목표 지점(3, 4)에 도달했는지 확인
        if maze[rr][rc] == 3 and maze[br][bc] == 4:
            return count  # 이동 횟수를 반환하며 종료

        else:
            # 빨간 공만 목표 지점에 도달한 경우
            if maze[rr][rc] == 3:
                red_reached = True
                blue_reached = False
            # 파란 공만 목표 지점에 도달한 경우
            elif maze[br][bc] == 4:
                red_reached = False
                blue_reached = True
            # 둘 다 목표에 도달하지 않은 경우
            else:
                red_reached = False
                blue_reached = False

        # 네 방향으로 이동 시도
        for i in range(4):
            if blue_reached:  # 파란 공이 목표에 도달한 경우
                r = [rr + dr[i], rc + dc[i]]  # 빨간 공 이동 시도
                if is_bounded(r, m, n):  # 미로 범위 확인
                    if not (is_wall(r, maze) or is_crashed(r, (br, bc)) or is_visited(r, vr)):
                        # 조건을 만족하면 새로운 상태를 큐에 추가
                        path.append([r[0], r[1], br, bc, vr, vb, count + 1])

            elif red_reached:  # 빨간 공이 목표에 도달한 경우
                b = [br + dr[i], bc + dc[i]]  # 파란 공 이동 시도
                if is_bounded(b, m, n):  # 미로 범위 확인
                    if not (is_wall(b, maze) or is_crashed(b, (rr, rc)) or is_visited(b, vb)):
                        # 조건을 만족하면 새로운 상태를 큐에 추가
                        path.append([rr, rc, b[0], b[1], vr, vb, count + 1])

            else:  # 둘 다 목표에 도달하지 않은 경우
                r = [rr + dr[i], rc + dc[i]]  # 빨간 공 이동 시도
                if is_bounded(r, m, n):  # 미로 범위 확인
                    if not (is_wall(r, maze) or is_visited(r, vr)):
                        for j in range(4):  # 파란 공의 모든 방향 이동 시도
                            b = [br + dr[j], bc + dc[j]]
                            if is_bounded(b, m, n):  # 미로 범위 확인
                                if not (is_wall(b, maze) or is_visited(b, vb) or is_crashed(b, r) or is_crossed(r, (br, bc), b, (rr, rc))):
                                    # 조건을 만족하면 새로운 상태를 큐에 추가
                                    path.append([r[0], r[1], b[0], b[1], vr, vb, count + 1])

    return 0  # 목표 지점에 도달할 수 없는 경우