[문제 바로가기] https://www.acmicpc.net/problem/19237
📌문제 설명
청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.
N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.
각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.
모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.
<그림 1>은 맨 처음에 모든 상어가 자신의 냄새를 뿌린 상태를 나타내며, <표 1>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 k = 4이다. 왼쪽 하단에 적힌 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 좌측 상단에 적힌 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호를 의미한다.
<그림 2>는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태이고, <그림 3>은 <그림 2>의 상태에서 한 칸 더 이동한 것이다. (2, 4)에는 상어 2과 4가 같이 도달했기 때문에, 상어 4는 격자 밖으로 쫓겨났다.
<그림 4>은 격자에 남아있는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태, <그림 5>는 <그림 4>에서 한 칸 더 이동한 상태를 나타낸다. 상어 2는 인접한 칸 중에 아무 냄새도 없는 칸이 없으므로 자신의 냄새가 들어있는 (2, 4)으로 이동했다. 상어가 이동한 후에, 맨 처음에 각 상어가 뿌린 냄새는 사라졌다.
이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.
입력
첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.
그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.
그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.
맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.
출력
1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.
💡 문제 풀이
상어 시리즈의 끝판왕(?) '어른 상어' 문제는 문제의 내용을 순서에 맞게 구현하는 '시뮬레이션' 유형의 문제다.
복잡해 보이지만 문제의 순서를 제대로 이해하면 쉽게 해결할 수 있다.
step 1)
변수 설정
- d : 상어의 이동을 위한 배열(위, 아래, 왼쪽, 오른쪽 순)
- tank : 상어가 움직이는 배열(NxN)
- sharks_d : 상어의 우선순위 방향을 알려줄 딕셔너리
- n_d(now_direction) : 현재 상어의 방향을 담은 배열
- survive : 상어의 생존 여부
- time : 걸린 시간
step 2)
문제를 해결하기 위해 상어의 움직임을 단계화 하였다.
- 인접한 칸 중 이동이 가능한 칸을 찾는다.(우선순위 고려) → find 함수
- 1번에서 찾은 칸으로 상어들이 각자 이동할 때, 자신보다 작은 번호의 상어와 만나면 번호가 큰 상어는 쫓겨난다. 그렇지 않을 경우 자신의 냄새를 칸에 뿌린다. → move 함수
- 이동 후 상어들이 남긴 냄새의 시간을 모두 -1 해준다. → delete 함수
step 3)
find 함수로 다음에 이동할 칸을 찾는다.
1번부터 M번까지 아직 배열(tank)안에 남아있는 상어에 대해서 다음에 이동할 칸을 찾는다.
- ready : 1번부터 M번까지의 상어들이 다음에 이동할 칸의 정보를 담는 배열
※ ready에는 (상어의 번호, 이동할 행좌표, 이동할 열좌표, 방향)의 값을 담는다.
우선순위 방향을 고려하여 이동할 칸을 찾는데 이 때, 이동할 칸이 없다면 자신이 지나온 칸으로 되돌아가야 함을 주의한다. → same에 자신이 지나온 칸 정보를 담는다.
만약, 이동할 수 있는 칸이 여러개가 있다면 가장 우선순위가 높은 칸으로 이동한다. → possible에서 첫 번째 정보를 ready에 담는다.
- possible : 인접한 칸 중 이동 가능한 칸을 담는 배열
step 4)
move 함수를 이용하여 상어를 이동시킨다.
ready에는 1번부터 M번까지 오름차순으로 상어의 이동정보가 담겨져 있다.
따라서, 이동 중에 큰 번호의 상어가 작은 번호의 상어와 같은 칸에서 만나게 되면 큰 번호의 상어를 쫓아낸다.
또한, move 함수 다음 delete 함수를 통해서 냄새의 시간(?)을 -1할 예정이므로 처음 냄새의 값을 k+1로 해준다.
step 5)
delete 함수를 사용하여 상어가 지나온 영역의 냄새의 시간을 -1 해준다.
냄새의 시간이 1보다 크면 -1을 해주고, 1이라면 [0, 0]의 값을 주어 흔적을 없앤다.
코드는 다음과 같다.
import sys
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def find(s):
for r in range(N):
for c in range(N):
if tank[r][c][0] == s and tank[r][c][1] == k:
turn = sharks_d[s][n_d[s]-1]
same = ''
possible = []
for t in turn:
nr = r + d[t-1][0]
nc = c + d[t-1][1]
if 0 <= nr < N and 0 <= nc < N:
if tank[nr][nc][0] == 0:
possible.append((s, nr, nc, t))
elif tank[nr][nc][0] == s and not same:
same = (s, nr, nc, t)
if len(possible):
ready.append(possible[0])
else:
ready.append(same)
return
def delete():
global N
for r in range(N):
for c in range(N):
if tank[r][c][0]:
if tank[r][c][1] == 1:
tank[r][c] = [0, 0]
else:
tank[r][c][1] -= 1
def move(ready):
for r in ready:
if tank[r[1]][r[2]][0] and tank[r[1]][r[2]][0] < r[0]:
survive[r[0]] = 0
continue
tank[r[1]][r[2]] = [r[0], k+1]
n_d[r[0]] = r[3]
N, M, k = map(int, input().split())
tank = [[[0, 0] for _ in range(N)] for _ in range(N)]
for r in range(N):
temp = list(map(int, input().split()))
for c in range(len(temp)):
if temp[c]:
tank[r][c] = [temp[c], k]
n_d = [0] + list(map(int, input().split())) # 상어 현재 방향
sharks_d = {} # 상어 우선순위 방향
for m in range(M):
before = [list(map(int, sys.stdin.readline().split())) for _ in range(4)]
sharks_d[m+1] = before
survive = [0] + [1] * (M) # 상어 생존 여부
time = 0 # 걸린 시간
while True:
ready = []
for s in range(1, 1+M):
if survive[s]:
find(s)
move(ready)
delete()
time += 1
if sum(survive) == 1:
break
if time > 1000:
break
print(-1 if time > 1000 else time)상어가 동시에 움직이기 때문에 같은 칸에서 충돌하는 경우가 발생한다...
처음에는 1번부터 바로바로 넣어주다보니 다음 번호에서 이동하지 못하는 칸으로 인식하여 원하지 않는 결과를 얻었었다.
동시에 모든 객체들이(?) 이동하면서 충돌이 생기는 문제의 경우 미리 후보들을 다 뽑아놓고 비교하는 방식으로 시도해보자.
