[python] 코드트리 - 코드트리 빵

문제

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

빵을 구하고자 하는 m명의 사람이 있는데, 1번 사람은 정확히 1분에, 2번 사람은 정확히 2분에, ..., m번 사람은 정확히 m 분에 각자의 베이스캠프에서 출발하여 편의점으로 이동하기 시작합니다.

 

좌표에서 1로 표시된 곳이 베이스캠프 후보입니다. 

 

각 사람 별 베이스 캠프는 자신이 가야하는 편의점 까지 최단 거리로 도달 할 수 있는 베이스 캠프 중 1곳을 선택하며, 만약 후보가 여러 곳이라면 그 중 행이 작은 곳을, 행이 같다면 열이 작은 곳을 베이스 캠프로 지정합니다.

 

 1번 사람이 가고 싶은 편의점과 가장 가까운 베이스캠프는 (2, 1)의 베이스캠프, (2, 5)의 베이스캠프 두 가지 입니다. 이 둘은 행이 같지만 (2, 1)의 베이스캠프가 열이 더 작기 때문에 해당 베이스캠프로 1번 사람이 이동합니다.

 

 

시간이 흐르면 다음과 같은 순서로 편의점으로 이동하기 시작합니다.

1. 격자에 있는 사람들 모두가 본인이 가고 싶은 편의점 방향을 향해서 1 칸 움직입니다. 최단거리로 움직이며 최단 거리로 움직이는 방법이 여러가지라면 ↑, ←, →, ↓ 의 우선 순위로 움직이게 됩니다. (최단거리 = 맨해튼 거리)

2. 만약 사람이 편의점에 도착한다면 해당 편의점에서 멈추게 되고, 이때부터 다른 사람들은 해당 편의점이 있는 칸을 지나갈 수 없습니다.

3. 현재 시간이 t분이고 t ≤ m를 만족한다면, t번 사람은 자신이 가고 싶은 편의점과 가장 가까이 있는 베이스 캠프에 들어갑니다. 

사람이 베이스 캠프에 들어가게 되면 해당 칸은 다른 사람은 지나 갈 수 없습니다.

 

여기서 주의 할 점은 초기 상태는 모든 사람은 격자 외부에 있다는 가정입니다.  즉, 시간이 1분 지난 시점에서는 1번과 2번은 일어나지 않습니다. 

1분이 지난 시점의 격자 상태(좌), 2분이 지난 시점의 격자 상태(우)

 

 

 

풀이

주어진 문제는 크게 세 단계로 나눌 수 있습니다.

1. 사용자 이동: 각 사용자는 자신의 목표 편의점으로 한 칸씩 움직이며, 최단 경로를 따라 이동합니다.
2. 편의점 점유 처리: 사용자가 목표 편의점에 도착하면 해당 편의점은 더 이상 다른 사용자가 들어갈 수 없도록 막아줍니다.
3. 베이스 캠프 진입: 새로운 사용자가 베이스 캠프에 진입하고, 이로부터 편의점까지 이동을 시작합니다.

 

 

1. 사용자 이동

각 사용자는 자신의 목표 편의점으로 이동하는데, 이를 위해 BFS(너비 우선 탐색) 알고리즘을 사용하여 편의점까지의 최단 경로를 찾습니다. 매 턴마다 사용자는 한 칸씩만 이동할 수 있으며, 이동 후 사용자가 도착한 위치를 업데이트합니다.

def move_user(arr: List[List[int]], start: Tuple[int, int], end: Tuple[int, int]) -> Tuple[int, int]:
    """
    사용자를 시작 위치에서 목표 위치로 이동시킵니다.
    BFS를 사용하여 최단 경로를 찾고, 한 칸씩 이동합니다.
    """
    n = len(arr)
    queue = deque([(start, [])])
    visited = set([start])

    while queue:
        (y, x), path = queue.popleft()
        if (y, x) == end:
            return path[0] if path else start  # 이동할 칸이 없으면 제자리

        for d in range(4):
            ny, nx = y + DY[d], x + DX[d]
            if 0 <= ny < n and 0 <= nx < n and arr[ny][nx] != -1 and (ny, nx) not in visited:
                visited.add((ny, nx))
                new_path = path + [(ny, nx)] if path else [(ny, nx)]
                queue.append(((ny, nx), new_path))

    return start  # 이동할 수 없는 경우 제자리

 

 

2. 편의점 점유 처리

사용자가 편의점에 도착하면 해당 위치를 차단하여 다른 사용자가 접근하지 못하게 합니다. 이를 위해 격자 배열의 해당 좌표를 -1로 표시하여 출입을 막습니다.

# 도착한 사용자 처리 (편의점 차단)
for y, x in no_access_pos:
    arr[y][x] = -1  # 편의점 위치 차단

 

 

3. 베이스 캠프 진입

새로운 사용자는 베이스 캠프에서 출발합니다. 이때 가장 가까운 베이스 캠프를 찾기 위해 또 한 번 BFS를 사용합니다. 가장 가까운 베이스 캠프는 첫 번째로 탐색되는 캠프입니다.

def get_first_base_camp(arr, start):
    """
    시작 위치에서 가장 가까운 베이스 캠프를 찾습니다.
    BFS를 통해 베이스 캠프를 탐색하고, 가장 가까운 캠프의 위치를 반환합니다.
    """
    n = len(arr)
    distances = [[float('inf')] * n for _ in range(n)]
    distances[start[0]][start[1]] = 0
    pq = [(0, start)]

    while pq:
        dist, (y, x) = heapq.heappop(pq)

        if distances[y][x] < dist:
            continue

        if arr[y][x] == 1:  # 베이스 캠프 발견
            return y, x

        for d in range(4):
            ny, nx = y + DY[d], x + DX[d]
            if 0 <= ny < n and 0 <= nx < n and arr[ny][nx] != -1:
                new_dist = dist + 1
                if new_dist < distances[ny][nx]:
                    distances[ny][nx] = new_dist
                    heapq.heappush(pq, (new_dist, (ny, nx)))

    return -1, -1  # 베이스 캠프가 없을 경우

 

 

코드

from collections import deque
from typing import List, Tuple, Dict
import heapq

# 상, 좌, 우, 하 방향으로의 이동을 나타내는 상수
DX = [0, -1, 1, 0]
DY = [-1, 0, 0, 1]


def read_input() -> Tuple[int, int, List[List[int]], Dict[int, Tuple[int, int]]]:
    """
    사용자 입력을 읽어 게임 초기 상태를 설정합니다.
    """
    n, m = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    convs = {i: tuple(map(lambda x: int(x) - 1, input().split())) for i in range(m)}
    return n, m, arr, convs


def get_base_camps(arr: List[List[int]]) -> List[Tuple[int, int]]:
    """
    격자에서 모든 베이스 캠프의 위치를 찾습니다.
    """
    return [(i, j) for i in range(len(arr)) for j in range(len(arr)) if arr[i][j] == 1]


def move_user(arr: List[List[int]], start: Tuple[int, int], end: Tuple[int, int]) -> Tuple[int, int]:
    """
    사용자를 시작 위치에서 목표 위치로 이동시킵니다.
    """
    n = len(arr)
    queue = deque([(start, [])])
    visited = set([start])

    while queue:
        (y, x), path = queue.popleft()
        if (y, x) == end:
            return path[0] if path else start

        for d in range(4):
            ny, nx = y + DY[d], x + DX[d]
            if 0 <= ny < n and 0 <= nx < n and arr[ny][nx] != -1 and (ny, nx) not in visited:
                visited.add((ny, nx))
                new_path = path + [(ny, nx)] if path else [(ny, nx)]
                queue.append(((ny, nx), new_path))

    return start



def get_first_base_camp(arr, start):
    """
    시작 위치에서 가장 가까운 베이스 캠프를 찾습니다.
    """
    n = len(arr)
    distances = [[float('inf')] * n for _ in range(n)]
    distances[start[0]][start[1]] = 0
    pq = [(0, start)]

    while pq:
        dist, (y, x) = heapq.heappop(pq)

        if distances[y][x] < dist:
            continue

        if arr[y][x] == 1:
            return y, x

        for d in range(4):
            ny, nx = y + DY[d], x + DX[d]
            if 0 <= ny < n and 0 <= nx < n and arr[ny][nx] != -1:
                new_dist = dist + 1
                if new_dist < distances[ny][nx]:
                    distances[ny][nx] = new_dist
                    heapq.heappush(pq, (new_dist, (ny, nx)))

    return -1, -1


def main():
    """
    메인 함수: 게임 로직을 실행합니다.
    """
    n, m, arr, convs = read_input()
    users: List[Tuple[int, int]] = []
    answer = 0
    cnt = 0

    while cnt < m:
        no_access_pos = []

        # 유저 이동
        for idx, user in enumerate(users):
            conv = convs[idx]
            # 이미 도착했으면 continue
            if conv == user:
                continue

            user = move_user(arr, tuple(user), conv)
            users[idx] = user
            if conv == tuple(user):
                cnt += 1
                no_access_pos.append(user)

        # 이동 불가 처리
        for y, x in no_access_pos:
            arr[y][x] = -1

        if len(users) == len(convs):
            answer += 1
            continue

        # 베이스캠프로 이동
        conv = convs[len(users)]
        y, x = get_first_base_camp(arr, conv)
        users.append((y, x))
        arr[y][x] = -1

        # 턴 증가
        answer += 1

    print(answer)


if __name__ == '__main__':
    main()