어른 상어
문제링크
https://www.acmicpc.net/problem/19237
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import sys
sys.stdin = open('input.txt','r')
from copy import deepcopy
n, m, k = map(int,input().split())
# 상어의 번호를 담느 격자
board = [[int(x) for x in input().split()] for _ in range(n)]
# 냄새 영역 표시
# [0,-1] 의 의미는 냄새가 0 이고 -1 은 그 냄새 뿌린 상어의 번호가 올자리
smell = [[[0,-1]]*n for _ in range(n)]
# 각 상어의 방향과 우선순위 정보를 담는 ARR
shark_dir = list(map(int,input().split()))
for i in range(m):
shark_dir[i] = [shark_dir[i]]
for _ in range(4):
shark_dir[i].append(list(map(int,input().split())))
# shark_dir = [방향, [우선순위들...] ]
# print(shark_dir)
cnt = 0
dir = [(-1,0),(1,0),(0,-1),(0,1)]
temp = 0
while True:
if temp == m-1 : # 1개만 남았을 경우 BREAK
print(cnt)
break
if cnt >= 1000:
print('-1')
break
# 현재 상어가 위치한 자리에 냄새를 뿌린다
for i in range(n):
for j in range(n):
if board[i][j] != 0:
smell[i][j] = [k,board[i][j]]
new_board = deepcopy(board)
for i in range(n):
for j in range(n):
if board[i][j] != 0:
d, up, down, left, right = shark_dir[board[i][j]-1]
dir_arr = [up, down, left, right]
flag = 0
for p in range(4):
dx, dy = dir[dir_arr[d-1][p] - 1]
# 인접한 영역에 냄새가 0 인 경우 우선순위를 고려
if -1 < i+dx < n and -1 < j+dy < n and smell[i+dx][j+dy] == [0,-1]:
# 이동하는 자리에 어떠한 상어도 없을경우
if new_board[i+dx][j+dy] == 0:
new_board[i+dx][j+dy] = board[i][j]
new_board[i][j] = 0
# 이동하는 자리에 다른 상어가 있을경우 넘버를 비교해서 작은것을 위치시키고 temp 를 +1 시킨다 하나 격자밖으로 쫓아내지니까
else:
if new_board[i+dx][j+dy] > board[i][j]:
new_board[i+dx][j+dy] = board[i][j]
temp += 1
new_board[i][j] = 0
shark_dir[board[i][j]-1][0] = dir_arr[d-1][p]
flag = 1
break
else:
# 인접한 영역에 냄새가 0 인 곳이 없을 경우
for p in range(4):
dx, dy = dir[dir_arr[d-1][p] - 1]
# smell[i+dx][j+dy][1]가 자신의 넘버와 같은 경우 즉 자기의 냄새인 영역
if -1 < i+dx < n and -1 < j+dy < n and smell[i+dx][j+dy][1] == board[i][j]:
new_board[i+dx][j+dy] = board[i][j]
new_board[i][j] = 0
shark_dir[board[i][j]-1][0] = dir_arr[d-1][p]
break
board = deepcopy(new_board)
# 그리고 냄새 영역 이동했으니까 하나씩 줄여주기
for i in range(n):
for j in range(n):
if smell[i][j][1] != -1:
smell[i][j][0] -= 1
if smell[i][j][0] == 0:
smell[i][j] = [0,-1]
# print(board)
# print(smell)
cnt += 1
해설
사실 이 문제를 푸는데 정말 몇번을 엎은 문제이다. 😅
먼저 상어의 번호를 볼 수 있는 board 그리고 냄새에 대한 정보를 알려주는 smell이 있다. smell 같은 경우 [냄새의크기, 상어번호] 로 만들어서 인접한 영역에 냄새가 0 인 자리가 없을 경우 자신의 번호와 같은 냄새 즉, 자신이 남긴 냄새 영역으로 이동할 수 있도록 만들었다. 그리고 이동한자리에 다른 상어가 있을 경우 한마리가 사라지므로 temp 값을 1을 차감하였다. 그리고, new_board를 만들어서 상어를 하나씩 이동한 뒤에 이동을 마치면 deepcopy 를 이용해board를 new_board 값으로 초기화해 주었다. 이동을 한 뒤에는, smell 이차원 배열을 탐색해가며 하나씩 값을 줄여주고 줄였을때 0 이 된 자리는 다시 초기 값인 [0, -1] 로 초기화 해주었다.