19237. 어른상어 문제 바로가기
※ 주의 tip!
테스트 케이스가 다 맞고 제출시 6%에서 틀렸습니다가 뜬다면 시간 조건만 수정해주면 된다!!
문제 중 일부 부분 1000가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.
테스트 케이스가 다 맞고 제출시 6%에서 틀렸습니다가 뜬다면 시간 조건만 수정해주면 된다!!
문제 중 일부 부분 1000가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다. 을 보고 1000초까지 괜찮은 건 줄 알았는 데 1000초 포함이였습니다~
1
2
3
4
# 고치기 전 before
if time > 1000; break (X)
# 고친 뒤 after
if time ≥ 1000; break (이렇게 고쳤더니 통과됐어요!)
해결 방법
함수를 이용한 것이 아니라 코드의 흐름대로(위에서 부터 아래로) 주석보시면서 이해하시면 좋을 것 같아요~!
상어 번호와 방향은 모두 0부터 시작되도록 초기 입력을 받을 때 1을 빼주었습니다.
먼저 원하는 형태로 ocean에 저장했습니다.
1
2
3
4
5
6
7
ocean = [
[0, 0, 0, 0, [2, 4, 2]]
[0, [1, 4, 3], 0, 0, 0]
[[0, 4, 3], 0, 0, 0, [3, 4, 0]]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
]
위의 형태는 처음 입력받은 값을 다음과 같이 저장했습니다.
즉 ocean 원소의 형태는 3가지가 존재할 수 있습니다.
- 0 : 상어도 x, 냄새도 x는 영역
- [상어번호, 남은 시간] : 상어는 없고 냄새가 남아있는 경우
- [상어번호, k, 방향] : 상어가 있는 경우
next*ocean = [[0] * N for * in range(N)] 초기화된 리스트에 아래 1, 2번 과정을 실행합니다.
1. 상어가 없고 냄새가 남아있는 경우 남은 시간 -1을 해준 것을 저장하기
2. 상어가 있는 경우 현 위치를 [상어번호, k - 1] 형태로 저장한 뒤 이동할 위치를 찾아 [상어번호, k, 방향]의 형태로 저장하기
→ 이때 next_ocean에 이미 상어가 있다면 크기를 비교해서 번호가 작은 상어로 저장하고 out 변수에 + 1을 시켜 격자 위로 사라진 상어를 카운트 하기
deepcopy를 이용하여 ocean에 next_ocean을 저장하고 위 과정을 반복하며 상어가 1마리 남았을 경우 time을 출력하도록 합니다.
if time ≥ 1000인 경우 time = -1 상태로 작동을 멈추면 끝납니다!
구현한 코드
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
82
83
84
85
86
87
88
89
from copy import deepcopy
# 입력을 받기
N, M, k = map(int, input().split())
ocean = [[0] * N for _ in range(N)]
temp = [list(map(int, input().split())) for _ in range(N)]
temp_dir = list(map(int, input().split()))
# ocean 리스트에 원하는 형태로 저장하기
# 상어가 있으면 [번호, k, 방향] => 번호, 방향 모두 0부터 시작하도록 설정
# 상어가 없지만 냄새가 남아있다면 [번호, 남은 시간]
# 상어가 없고 냄새도 없다면 0
for i in range(N):
for j in range(N):
if temp[i][j] != 0:
ocean[i][j] = [temp[i][j] - 1, k, temp_dir[temp[i][j] - 1] - 1]
# 상어마다 주어지는 우선순위 방향 저장하기 => 방향 모두 0부터 시작하도록 설정
shark_dir = [] * M
for _ in range(M):
temp = []
for t1 in range(4):
temp.append(list(map(int, input().split())))
for t2 in range(4):
temp[t1][t2] -= 1
shark_dir.append(temp)
dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
out = 0 # 상어가 격자 밖으로 쫓겨나는 경우 cnt
time = 0 # 얼마나 지났는지 체크해줄 변수
while out < M - 1:
if time >= 1000: # 조건 중요!
time = -1
break
time += 1
next_ocean = [[0] * N for _ in range(N)]
for y in range(N):
for x in range(N):
# 1. 남아있는 냄새 유지 시간 줄이기
# 주의 : next_ocean에 상어 있는 경우 건드리면 X
if ocean[y][x] != 0 and len(ocean[y][x]) == 2 and ocean[y][x][1] > 1:
if next_ocean[y][x] != 0 and len(next_ocean[y][x]) == 3: # 상어가 있으면 냄새로 없애면 안된다!!
pass
else:
next_ocean[y][x] = [ocean[y][x][0], ocean[y][x][1] - 1]
# 2. 상어 이동시키기
if ocean[y][x] != 0 and len(ocean[y][x]) == 3: # 상어가 있는 경우
# 2-1. 현재 자리 냄새 기록하기
if k - 1 > 0:
next_ocean[y][x] = [ocean[y][x][0], k - 1]
# 2-2. 이동할 자리 탐색하기
num, sd = ocean[y][x][0], ocean[y][x][2]
frag = True # 냄새 없는 칸이 없는 경우 true 유지
frag_temp = []
for d in range(4):
nd = shark_dir[num][sd][d]
ny, nx = y + dir[nd][0], x + dir[nd][1]
if 0 <= ny < N and 0 <= nx < N and ocean[ny][nx] == 0:
frag = False
if next_ocean[ny][nx] != 0 and len(next_ocean[ny][nx]) > 2:
# 한칸에 두마리 상어가 만난 경우
out += 1
if next_ocean[ny][nx][0] > num:
next_ocean[ny][nx] = [num, k, nd]
else:
next_ocean[ny][nx] = [num, k, nd]
break
elif 0 <= ny < N and 0 <= nx < N and ocean[ny][nx] != 0 and ocean[ny][nx][0] == num:
frag_temp.append([ny, nx, nd]) # 자신의 냄새가 있는 위치 저장하기
if frag : # 주위에 빈칸이 없는 경우
# 자신 냄새가 있는 칸으로 이동시키기
ny, nx, nd = frag_temp.pop(0)
if next_ocean[ny][nx] != 0 and len(next_ocean[ny][nx]) > 2:
# 한칸에 두마리 상어가 만난 경우
out += 1
if next_ocean[ny][nx][0] > num:
next_ocean[ny][nx] = [num, k, nd]
else:
next_ocean[ny][nx] = [num, k, nd]
ocean = deepcopy(next_ocean)
print(time)