문제
$N \times N$ 격자판에 $M$마리의 상어가. 각 상어는 방향과 번호를 갖는다. 매 초 다음의 일들이 일어난다.
- 먼저, 각 상어가 있는 칸에 그 상어의 냄새가 뿌려진다. 이 냄새는 $K$초 뒤에 사라진다.
- 그 다음, 상어들이 움직이는데, 모든 상어는 동시에 움직인다. 인접한 냄새가 없는 칸이 있다면 그 칸으로 움직이고, 없다면 자신의 냄새가 있는 칸으로 움직인다. 만약 가능한 칸이 여러개라면 우선순위대로 움직인다.
- 모든 상어가 움직인 다음, 만약 둘 이상의 상어가 겹쳐있다면 번호가 가장 작은 상어만 남고 나머지는 쫓겨난다.
이때, 1번 상어만 남게 되는 시간을 구하는 문제이다.
접근
으레 그렇듯이 구현만 잘 하면 된다. 여러 방법으로 구현할 수 있겠지만, 나는 다음과 같이 구현하였다.
- 상어의 현재 위치를 저장하는 2차원
shark리스트, 남아 있는 냄새를[번호, 남은 시간]꼴로 저장할 3차원board리스트, 각 상어의 방향을 저장할direction리스트, 각 상어의 방향 우선순위를 저장해 놓는prefer리스트를 만든다. 또, 상어 수를 저장할count를 $M$으로 초기화 해 둔다. - $t=1$부터 $t=1000$까지 다음을 반복한다:
shark리스트를 돌면서 상어들의 현재 위치를 찾아서,board리스트의 각 위치에 남은시간 $K$짜리 냄새를 만든다.- 그 다음 상어를 움직이는데, 먼저 상어가 한번에 움직이도록 하기 위해 모든 칸이 빈 칸, 즉
[-1,-1]으로 저장되어있는new_board리스트를 만든다. - 각 상어에 대해서, 만약 아직 존재한다면(
shark[i][0]!=-1)direction리스트에서 현재 방향을 가져오고, 이를 이용해prefer리스트의 네 방향을 우선순위 순서대로 살펴본다.- 만약 냄새가 없는 칸을 만나면, 그 칸이 가장 우선순위가 높은 칸이므로 즉시 break해준다.
- 자신의 냄새가 있는 칸을 만나면, 가장 먼저 만나는 하나만 저장해 놓는다.
- 냄새가 없는 칸이 없었다면, 자신의 냄새였던 칸을 목표로 한다. 없었다면 냄새가 없는 그 칸이 목표이다.
- 목표하는 칸으로 상어를 이동시킨다.
direction을 바꿔주고,shark리스트에 저장된 위치를 바꿔준다. new_board리스트의 새 위치에 상어 번호를[num, -1]꼴로 적어준다. 만약 이미 그 자리에 상어 번호가 적혀있다면, 두 번호를 비교해서 낮은 번호를 놔두고, 높은 번호는 없애준다.shark리스트에[-1,-1]을 넣어 쫓겨났음을 표시한다. 이때count도 1 줄어든다.
- 마지막으로,
board리스트에서 냄새를 1씩 줄여new_board로 옮겨준다. new_board를board에 새로 assign한다.- 만약 상어 수가 1이라면, 현재 시간을 출력하고 끝낸다.
- $t=1000$까지 상어 수가 여러 마리라면, -1을 출력한다.
주의할 점
비어있는 칸, 잡아먹힌 상어, 냄새 등을 어떤 형식으로 저장할 지 잘 생각해보아야 한다.
1번 상어만 남는 경우와 상어 수가 1인 상태는 완벽히 동일하므로, 매 루프마다 각 상어의 상태를 확인할 필요 없이 상어 수만 세어도 충분하다.
Code
링크# https://www.acmicpc.net/problem/19237
# Implementation
from sys import stdin
dx = [-1, 1, 0, 0] # up, down, left, right
dy = [0, 0, -1, 1]
n, m, k = map(int, stdin.readline().split())
shark = [[] for _ in range(m)]
for i in range(n):
line = list(map(int, stdin.readline().split()))
for j in range(n):
if line[j] != 0:
shark[line[j] - 1] = [i, j]
board = [[[-1, -1] for _ in range(n)] for _ in range(n)] # initially there's no fragrance.
direction = list(map(lambda x: int(x) - 1, stdin.readline().split()))
prefer = [[list(map(lambda x: int(x) - 1, stdin.readline().split())) for _ in range(4)] for _ in range(m)]
count = m
for t in range(1, 1001):
# first, make smell
for i in range(m):
row, col = shark[i]
if row == -1:
continue
board[row][col] = [i, k] # shark number, duration
# then, move
new_board = [[[-1, -1] for _ in range(n)] for _ in range(n)]
for i in range(m):
row, col = shark[i]
if row == -1:
continue
d = direction[i]
target_direction = None
my_fragrance = None
# first, find for no-fragrance cell
for target in prefer[i][d]:
nrow = row + dx[target]
ncol = col + dy[target]
if 0 <= nrow < n and 0 <= ncol < n:
if board[nrow][ncol][0] == -1: # no-fragrance
target_direction = target
break
if board[nrow][ncol][0] == i and my_fragrance is None: # my-fragrance
my_fragrance = target
# if there was no empty cell, go to my-fragrance
if target_direction is None:
target_direction = my_fragrance
# actually moving
nrow = row + dx[target_direction]
ncol = col + dy[target_direction]
direction[i] = target_direction
shark[i] = [nrow, ncol]
# when two sharks collide
if new_board[nrow][ncol][0] != -1:
other = new_board[nrow][ncol][0]
count -= 1
# lose
if other < i:
shark[i] = [-1, -1]
else:
shark[other] = [-1, -1]
new_board[nrow][ncol] = [i, -1]
else:
new_board[nrow][ncol] = [i, -1]
# finally, decrease smell.
for i in range(n):
for j in range(n):
num, dur = board[i][j]
if num != -1 and dur > 1:
new_board[i][j] = [num, dur - 1]
board = new_board
if count == 1:
print(t)
break
else:
print(-1)
