728x90
조건
- 빵을 구하고자 하는 m명의 사람이 있는데, 1번 사람은 정확히 1분에, 2번 사람은 정확히 2분에, .. , m번 사람은 정확히 m분에 각자의 베이스캠프에서 출발하여 편의점으로 이동하기 시작
- 사람들은 출발 시간이 되기 전까지 격자 밖에 나와잇으며, 사람들이 목표로하는 편의점은 모두 다르다. 격자의 크기는 n * n
- 코드트리 빵을 구하고 싶은 사람들은 아래와 같은 방법으로 움직이며, 3가지 행동은 총 1분 동안 진행되며, 정확히 1, 2, 3 순서로 진행됨
- 격자에 있는 사람들 모두가 본인이 가고 싶은 편의점 방향을 향해서 1 칸 움직입니다. 최단거리로 움직이며 최단 거리로 움직이는 방법이 여러가지라면 ↑, ←, →, ↓ 의 우선 순위로 움직이게 됩니다. 여기서 최단거리라 함은 상하좌우 인접한 칸 중 이동가능한 칸으로만 이동하여 도달하기까지 거쳐야 하는 칸의 수가 최소가 되는 거리를 뜻합니다.
- 만약 편의점에 도착한다면 해당 편의점에서 멈추게 되고, 이때부터 다른 사람들은 해당 편의점이 있는 칸을 지나갈 수 없게 됩니다. 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.
- 현재 시간이 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)
728x90
'ALGORITHM > 정렬, 탐색,구현' 카테고리의 다른 글
[백준 1744번] 파이썬 - 수 묶기 (0) | 2023.04.15 |
---|---|
[프로그래머스 Lv1] 파이썬 - 달리기 경주 (0) | 2023.04.10 |
[코드트리] 파이썬 - 예술성 (0) | 2023.04.07 |
[백준 20056번] 파이썬 - 마법사 상어와 파이어볼 (0) | 2023.04.06 |
[백준 14503번] 파이썬 - 로봇 청소기 (0) | 2023.04.04 |