[코드트리] 파이썬 - 코드트리 빵

코드트리 - 코드트리 빵

조건

• 빵을 구하고자 하는 m명의 사람이 있는데, 1번 사람은 정확히 1분에, 2번 사람은 정확히 2분에, .. , m번 사람은 정확히 m분에 각자의 베이스캠프에서 출발하여 편의점으로 이동하기 시작
• 사람들은 출발 시간이 되기 전까지 격자 밖에 나와잇으며, 사람들이 목표로하는 편의점은 모두 다르다. 격자의 크기는 n * n
• 코드트리 빵을 구하고 싶은 사람들은 아래와 같은 방법으로 움직이며, 3가지 행동은 총 1분 동안 진행되며, 정확히 1, 2, 3 순서로 진행됨
  1. 격자에 있는 사람들 모두가 본인이 가고 싶은 편의점 방향을 향해서 1 칸 움직입니다. 최단거리로 움직이며 최단 거리로 움직이는 방법이 여러가지라면 ↑, ←, →, ↓ 의 우선 순위로 움직이게 됩니다. 여기서 최단거리라 함은 상하좌우 인접한 칸 중 이동가능한 칸으로만 이동하여 도달하기까지 거쳐야 하는 칸의 수가 최소가 되는 거리를 뜻합니다.
  2. 만약 편의점에 도착한다면 해당 편의점에서 멈추게 되고, 이때부터 다른 사람들은 해당 편의점이 있는 칸을 지나갈 수 없게 됩니다. 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.
  3. 현재 시간이 t분이고 t ≤ m를 만족한다면, t번 사람은 자신이 가고 싶은 편의점과 가장 가까이 있는 베이스 캠프에 들어갑니다. 여기서 가장 가까이에 있다는 뜻 역시 1에서와 같이 최단거리에 해당하는 곳을 의미합니다. 가장 가까운 베이스캠프가 여러 가지인 경우에는 그 중 행이 작은 베이스캠프, 행이 같다면 열이 작은 베이스 캠프로 들어갑니다. t번 사람이 베이스 캠프로 이동하는 데에는 시간이 전혀 소요되지 않습니다.
• 이때부터 다른 사람들은 해당 베이스 캠프가 있는 칸을 지나갈 수 없게 됩니다.
• t번 사람이 편의점을 향해 움직이기 시작했더라도 해당 베이스 캠프는 앞으로 절대 지나갈 수 없음에 유의합니다.
• 마찬가지로 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.
  
  
  • 이미 사람들이 도착한 편의점이나 출발한 적이 있는 베이스캠프의 경우 움직일 때 절대 지나갈 수 없는 공간임을 유의합니다.
  • 사람들이 위와 같은 방식으로 움직일 때 총 몇 분 후에 모두 편의점에 도착하는지를 구하는 프로그램을 작성해보세요.

입력 형식

• 첫 번째 줄에는 격자의 크기 n과 사람의 수 m이 공백을 사이에 두고 주어집니다.
• 이후 n개의 줄에 걸쳐 격자의 정보가 주어집니다.
  • 각 줄에 각각의 행에 해당하는 n개의 수가 공백을 사이에 두고 주어집니다.
  • 0의 경우에는 빈 공간, 1의 경우에는 베이스캠프를 의미합니다.
• 이후 m개의 줄에 걸쳐 각 사람들이 가고자 하는 편의점 위치의 행 x, 열 y의 정보가 공백을 사이에 두고 주어집니다.
• 각 사람마다 가고 싶은 편의점의 위치는 겹치지 않으며, 편의점의 위치와 베이스캠프의 위치도 겹치지 않습니다.
  • 2 ≤ n ≤ 15
  • 1 ≤ m ≤ min(n2,30)
  • m ≤ 베이스 캠프의 개수 ≤ n2−m

접근 방법

• 구현, 시뮬레이션 문제이므로 문제에 나와있는 조건을 잘 찾아주면 된다.
• step 1,2,3으로 나누어 실행해준다.
• step1의 경우 bfs를 돌며 목적지까지의 최단거리를 구해준다.
  • 편의점위치를 기준으로 시작하여, 현재 사람의 위치를 기준으로 가장 작은 값으로 이동해주면된다.
• step2의 경우, 모든 사람을 돌며 현재 위치가 편의점이라면 arr 2로 만들어 주며 이동하지 못하게 한다.
• step3도 마찬가지고 편의점을 기준으로 bfs를 돌며 가장 가까운 베이스 캠프를 구해준다.
  • 이후 이동하지 못하게 표시

import sys  
from collections import deque  
sys.stdin = open('input.txt')  
INT_MAX = sys.maxsize  
EMPTY = (-1, -1)  

n, m = tuple(map(int, input().split()))  

grid = [  
    list(map(int, input().split()))  
    for _ in range(n)  
]  

cvs_list = []  
for _ in range(m):  
    x, y = tuple(map(int, input().split()))  
    cvs_list.append((x - 1, y - 1))  

people = [EMPTY] * m  
curr_t = 0  

dxs = [-1, 0, 0, 1]  
dys = [0, -1, 1, 0]  

step = [  
    [0] * n  
    for _ in range(n)  
]  

visited = [  
    [False] * n  
    for _ in range(n)  
]  

def in_range(x, y):  
    return 0 <= x and x < n and 0 <= y and y < n  



def can_go(x, y):  
    return in_range(x, y) and not visited[x][y] and grid[x][y] != 2  

def bfs(start_pos):  
    for i in range(n):  
        for j in range(n):  
            visited[i][j] = False  
            step[i][j] = 0  

    q = deque()  
    q.append(start_pos)  
    sx, sy = start_pos  
    visited[sx][sy] = True  
    step[sx][sy] = 0  

    while q:  
        x, y = q.popleft()  
  
        for dx, dy in zip(dxs, dys):  
            nx, ny = x + dx, y + dy  
            if can_go(nx, ny):  
                visited[nx][ny] = True  
                step[nx][ny] = step[x][y] + 1  
                q.append((nx, ny))  


def simulate():  
 
    for i in range(m):  
        if people[i] == EMPTY or people[i] == cvs_list[i]:  
            continue  

        px, py = people[i]  
        min_dist = INT_MAX  
        min_x, min_y = -1, -1  
        for dx, dy in zip(dxs, dys):  
            nx, ny = px + dx, py + dy  
            if in_range(nx, ny) and visited[nx][ny] and min_dist > step[nx][ny]:  
                min_dist = step[nx][ny]  
                min_x, min_y = nx, ny  

        people[i] = (min_x, min_y)  

    for i in range(m):  
        if people[i] == cvs_list[i]:  
            px, py = people[i]  
            grid[px][py] = 2  

    if curr_t > m:  
        return  

    bfs(cvs_list[curr_t - 1])  

    min_dist = INT_MAX  
    min_x, min_y = -1, -1  
    for i in range(n):  
        for j in range(n):  
            if visited[i][j] and grid[i][j] == 1 and min_dist > step[i][j]:  
                min_dist = step[i][j]  
                min_x, min_y = i, j  

    people[curr_t - 1] = (min_x, min_y)  
    print(people)  
    grid[min_x][min_y] = 2  


def end():  
    for i in range(m):  
        if people[i] != cvs_list[i]:  
            return False  

    return True  


while True:  
    curr_t += 1  
    simulate()  
    if end():  
        break  
print(curr_t)