[Python/Codetree] 코드트리 빵

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread/submissions?page=1&pageSize=20 

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

문제

최근 코드트리 빵이 전국적으로 인기를 얻어 편의점에서 해당 빵을 구하기 힘들어졌습니다. 빵을 구하고자 하는 m명의 사람이 있는데, 1번 사람은 정확히 1분에, 2번 사람은 정확히 2분에, ..., m번 사람은 정확히 m 분에 각자의 베이스캠프에서 출발하여 편의점으로 이동하기 시작합니다. 사람들은 출발 시간이 되기 전까지 격자 밖에 나와있으며, 사람들이 목표로 하는 편의점은 모두 다릅니다. 이 모든 일은 n*n 크기의 격자 위에서 진행됩니다.

코드트리 빵을 구하고 싶은 사람들은 다음과 같은 방법으로 움직입니다. 이 3가지 행동은 총 1분 동안 진행되며, 정확히 1, 2, 3 순서로 진행되어야 함에 유의합니다.

1. 격자에 있는 사람들 모두가 본인이 가고 싶은 편의점 방향을 향해서 1 칸 움직입니다. 최단거리로 움직이며 최단 거리로 움직이는 방법이 여러가지라면 ↑, ←, →, ↓ 의 우선 순위로 움직이게 됩니다. 여기서 최단거리라 함은 상하좌우 인접한 칸 중 이동가능한 칸으로만 이동하여 도달하기까지 거쳐야 하는 칸의 수가 최소가 되는 거리를 뜻합니다.
2. 만약 편의점에 도착한다면 해당 편의점에서 멈추게 되고, 이때부터 다른 사람들은 해당 편의점이 있는 칸을 지나갈 수 없게 됩니다. 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.
3. 현재 시간이 t분이고 t ≤ m를 만족한다면, t번 사람은 자신이 가고 싶은 편의점과 가장 가까이 있는 베이스 캠프에 들어갑니다. 여기서 가장 가까이에 있다는 뜻 역시 1에서와 같이 최단거리에 해당하는 곳을 의미합니다. 가장 가까운 베이스캠프가 여러 가지인 경우에는 그 중 행이 작은 베이스캠프, 행이 같다면 열이 작은 베이스 캠프로 들어갑니다. t번 사람이 베이스 캠프로 이동하는 데에는 시간이 전혀 소요되지 않습니다.
4. 이때부터 다른 사람들은 해당 베이스 캠프가 있는 칸을 지나갈 수 없게 됩니다. t번 사람이 편의점을 향해 움직이기 시작했더라도 해당 베이스 캠프는 앞으로 절대 지나갈 수 없음에 유의합니다. 마찬가지로 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.

아래와 같이 n = 5, m = 3, 베이스 캠프 4곳, 편의점 3곳이 주어진 경우에 대해서 생각해보겠습니다.

1분에는 격자 내에 아직 사람이 없기 때문에 1, 2번 행동은 진행되지 않으며 3번 행동부터 진행됩니다. 1번 사람이 가고 싶은 편의점과 가장 가까운 베이스캠프는 (2, 1)의 베이스캠프, (2, 5)의 베이스캠프 두 가지 입니다. 이 둘은 행이 같지만 (2, 1)의 베이스캠프가 열이 더 작기 때문에 해당 베이스캠프로 1번 사람은 이동하고, 앞으로 해당 칸으로는 사람이 절대 지나갈 수 없게 됩니다.

2분에는 1번 사람이 편의점을 향해 한 칸 움직이게 됩니다. 또, 2번 사람이 베이스 캠프에 도착합니다. 이 경우에도 최단 거리에 있는 베이스 캠프가 (4, 2), (5, 5) 두 가지인데, (4, 2)에 있는 베이스캠프가 행이 작기 때문에 (4, 2) 베이스캠프로 이동하게 됩니다.

3분에는 1번과 2번 사람 각각이 한 칸씩 이동하게 됩니다. 그 뒤 1번 사람이 편의점에 도착해, 앞으로 해당 칸으로는 사람이 절대 지나갈 수 없게 됩니다. 3번은 새로 베이스캠프에 도착하게 됩니다.

이러한 과정을 반복하면 모든 사람이 편의점에 도착할 때까지 총 7분이 걸리게 됩니다. 그 과정은 아래와 같습니다.

이미 사람들이 도착한 편의점이나 출발한 적이 있는 베이스캠프의 경우 움직일 때 절대 지나갈 수 없는 공간임을 유의합니다. (예시에서는 빨간색으로 표시되어 있습니다.)

사람들이 위와 같은 방식으로 움직일 때 총 몇 분 후에 모두 편의점에 도착하는지를 구하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에는 격자의 크기 n과 사람의 수 m이 공백을 사이에 두고 주어집니다.

이후 n개의 줄에 걸쳐 격자의 정보가 주어집니다. 각 줄에 각각의 행에 해당하는 n개의 수가 공백을 사이에 두고 주어집니다.
0의 경우에는 빈 공간, 1의 경우에는 베이스캠프를 의미합니다.

이후 m개의 줄에 걸쳐 각 사람들이 가고자 하는 편의점 위치의 행 x, 열 y의 정보가 공백을 사이에 두고 주어집니다.

각 사람마다 가고 싶은 편의점의 위치는 겹치지 않으며, 편의점의 위치와 베이스캠프의 위치도 겹치지 않습니다.

• 2 ≤ n ≤ 15
• 1 ≤ m ≤ min(n2,30)
• m ≤ 베이스 캠프의 개수 ≤ n2−m

출력 형식

모든 사람이 편의점에 도착하는 시간을 출력하세요.

문제 조건에 의해 어떠한 사람이 원하는 편의점에 도달하지 못하게 되는 경우는 절대 발생하지 않음을 가정해도 좋습니다.
또한, 이동하는 도중 동일한 칸에 둘 이상의 사람이 위치하게 되는 경우 역시 가능함에 유의합니다.

풀이

Code

from collections import deque

# 1. 이동을 위한 BFS 함수 정의
def move_bfs(px, py, sx, sy) :
    # 1-1. 빙문 여부 리스트를 생성해 현재 위치 방문 처리
    visited = [[False for _ in range(n+1)] for _ in range(n+1)]
    visited[px][py] = True
    # 1-2. 역추적을 위한 배열 생성
    back_x = [[0 for _ in range(n+1)] for _ in range(n+1)]
    back_y = [[0 for _ in range(n+1)] for _ in range(n+1)]
    # 1-3. 큐를 생성해 현재 위치 삽입
    queue = deque()
    queue.append((px, py))
    # 1-4.
    while queue :
        # 1-4-1. 위치 인덱스 반환
        x, y = queue.popleft()
        # 1-4-2. 편의점 위치에 도착한 경우 역추적 시작
        if (x, y) == (sx, sy) :
            # 한 칸 차이일 경우 x, y 반환
            if (back_x[sx][sy], back_y[sx][sy]) == (px, py) : return x, y
            # 이외의 경우
            else :
                # 역추적 인덱스 생성
                cx, cy = back_x[sx][sy], back_y[sx][sy]
                # while문을 통해 다음 위치 반환
                while (back_x[cx][cy], back_y[cx][cy]) != (px, py) :
                    cx, cy = back_x[cx][cy], back_y[cx][cy]
                return cx, cy
        # 1-4-3.
        for dir_x, dir_y in [(-1, 0), (0, -1), (0, 1), (1, 0)] :
            nx, ny = x + dir_x, y + dir_y
            # 예외 처리
            if nx < 1 or nx > n or ny < 1 or ny > n or graph[nx][ny] == 2: continue
            # 현재 위치에 방문한 적이 없는 경우
            if not visited[nx][ny] :
                # 방문 처리
                visited[nx][ny] = True
                # 역추적을 위한 배열 정보 입력
                back_x[nx][ny], back_y[nx][ny] = x, y
                # 큐에 다음 위치 삽입
                queue.append((nx, ny))
# 2. 이동함수 정의
def move() :
    # 2-1.
    for i in range(1, m+1) :
        # t <= i 일 경우 continue
        if time <= i : continue
        px, py = people[i]
        sx, sy = store[i]
        # bfs를 통해 이동할 위치 반환
        if (px, py) == (sx, sy) : continue
        px, py = move_bfs(px, py, sx, sy)
        # 이동
        people[i] = [px, py]
# 3. 편의점 도착 판별 함수 정의
def arrive_check() :
    # 3-1.
    for i in range(1, m+1) :
        # t <= i 일 경우 continue
        if time <= i : continue
        # 현재 위치가 편의점 위치이나 체킹이 안 되어 있는 경우
        if people[i] == store[i] and graph[people[i][0]][people[i][1]] != 2 :
            # 그래프 값 변경
            graph[people[i][0]][people[i][1]] = 2
# 4. 베이스 캠프 선정을 위한 BFS 정의
def camp_bfs(sx, sy) :
    # 4-1. 큐에 현재 위치 삽입
    queue = deque()
    queue.append((sx, sy))
    # 4-2. 배열 생성
    distance = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
    distance[sx][sy] = 0
    # 4-3.
    while queue :
        # 4-3-1. 인덱스 반환
        x, y = queue.popleft()
        # 4-3-2.
        for dir_x, dir_y in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
            nx, ny = x + dir_x, y + dir_y
            # 예외처리
            if nx < 1 or nx > n or ny < 1 or ny > n or graph[nx][ny] == 2 : continue
            # 현재 거리 + 1이 현재 인덱스값보다 작은 경우
            if distance[x][y] + 1 < distance[nx][ny] :
                # 값 변경
                distance[nx][ny] = distance[x][y] + 1
                # 큐에 다음 위치 삽입
                queue.append((nx, ny))
    # 4-4.
    cx, cy = 0, 0
    min_d = float('inf')
    for i in range(1, n+1) :
        for j in range(1, n+1) :
            # 베이스캠프인 경우
            if graph[i][j] == 1 :
                # 최소 거리 업데이트
                if distance[i][j] < min_d :
                    min_d = distance[i][j]
                    cx, cy = i, j
    # 4-5. 인덱스 반환
    return cx, cy
# 5. 베이스 캠프 선정 함수 정의
def select(t) :
    # 5-1. bfs를 통해 선정
    sx, sy = store[t]
    cx, cy = camp_bfs(sx, sy)
    # 5-2. 사람 위치 변동
    people[t] = [cx, cy]
    # 5-3. 그래프에 이동 불가 처리
    graph[cx][cy] = 2
# 6. 모두 편의점에 도착했는지 체크 함수 정의
def end_check() :
    # 6-1.
    for i in range(1, m+1) :
        if people[i] != store[i] : return False # 사람 위치와 편의점 위치가 다른 경우 False 반환
    # 6-2. True 반환
    return True

n, m = map(int, input().split())
graph = [[2 for _ in range(n + 1)]] + [([2] + list(map(int, input().split()))) for _ in range(n)]
store = [[]] + [list(map(int, input().split())) for _ in range(m)]
camp, people, check = [], [[]], [False for _ in range(m+1)]
people = [[0, 0] for _ in range(m+1)]
# 7. 시간 변수 생성
time = 1
# 8. 1초일 경우 베이스 캠프 지정
select(time)
# 9.
while True :
    # 9-1. 시간 증가
    time += 1
    # 9-2. 이동
    move()
    # 9-3. 편의점 도착 판별
    arrive_check()
    # 9-4.
    if time <= m :
        # 베이스캠프 선정
        select(time)
    # 9-5. 이외의 경우
    else :
        # 편의점에 모두 도착했다면 while문 탈출
        if end_check() : break
# 10. 결과 출력
print(time)