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
90
91
92
93
94
95
from collections import defaultdict
# 1: up, 2: down, 3: left, 4: right
class Solution:
def solve(self):
n,m,k = [int(item) for item in input().split()]
map = []
posDict = defaultdict(list)
scentDict = defaultdict(list)
offsetDict = {1:(-1,0),2:(1,0),3:(0,-1),4:(0,1)}
for i in range(n):
map.append([0]*n)
for i in range(n):
row = [int(item) for item in input().split()]
for j in range(n):
if row[j] != 0:
posDict[row[j]] = [i,j]
scentDict[(i,j)] = [row[j],k]
map[i][j] = row[j]
dirs = [int(item) for item in input().split()]
for i in range(m):
posDict[i+1].append(dirs[i])
dirsBySharkInfo = defaultdict(list)
for sharkNum in range(1,m+1):
curDir = 1
for i in range(4):
searchDir = [int(item) for item in input().split()]
dirsBySharkInfo[(sharkNum,curDir)] = searchDir
curDir+=1
duration = 0
while duration < 1000:
duration += 1
newItem = []
nextPosDict = defaultdict(list)
sharkList = list(posDict.keys())
for sharkNum in sharkList:
curPos = posDict[sharkNum]
curDir = curPos[2]
nextPos = curPos.copy()
sameScentPos = ()
isFind = False
for dir in dirsBySharkInfo[(sharkNum,curDir)]:
offset = offsetDict[dir]
nextPos = (curPos[0]+offset[0],curPos[1]+offset[1],dir)
if nextPos[0] < 0 or nextPos[0] > n-1 or nextPos[1] < 0 or nextPos[1] > n-1:
continue
keyVal = (nextPos[0],nextPos[1])
if scentDict[keyVal] != []:
if scentDict[keyVal][0] == sharkNum and sameScentPos == ():
sameScentPos = nextPos
else:
isFind = True
break
if isFind == False:
if sameScentPos == ():
nextPos = curPos
else:
nextPos = sameScentPos
nextPosDict[(nextPos[0],nextPos[1])].append((sharkNum,nextPos[2]))
posDict.pop(sharkNum)
for nextPos in nextPosDict.keys():
survivingSharkInfo = nextPosDict[nextPos][0]
if len(nextPosDict[nextPos]) >= 2:
survivingSharkInfo = sorted(nextPosDict[nextPos],key=lambda x:x[0])[0]
survivingSharkNum = survivingSharkInfo[0]
survivingSharkDir = survivingSharkInfo[1]
posDict[survivingSharkNum] = [nextPos[0],nextPos[1],survivingSharkDir]
scentDict[(nextPos[0],nextPos[1])] = [survivingSharkNum,k]
newItem.append((nextPos[0],nextPos[1]))
#update scent
temp = list(scentDict.keys()).copy()
for pos in temp:
if pos not in newItem:
scentDict[pos][1] -= 1
if scentDict[pos][1] == 0:
scentDict.pop(pos)
if len(posDict) == 1:
break
if len(posDict) == 1:
print(duration)
else:
print(-1)
Solution().solve()
이문제를 풀면서 특히 시간이 오래걸렸고, 왜 시간이 오래걸렸고 뇌정지가 왔는지에 대해서 생각해보았다. 내가 보기에 가장 큰 이유는 구현하기전에 확실하게 구현의 방향과 문제에 대해서 명확하게 머리속에 정리하지 않았기 때문이다. 보통 시뮬레이션 문제를 풀때, 시간을 아낄수 있는 방법은 풀기전에 구현에 대하여 명확하게 생각을 정리하는 것이다. 시뮬레이션 문제들은 정보량이 많고 개념도 낯선 경우가 많기때문에 문제를 먼저 정확하게 이해하는것이 중요하다. 문제를 정확하게 이해했다면 그에따라서 풀이를 어떻게 할지 고민해야하는데, 이때 어떤 자료구조,변수를 사용할것인지, 왜 사용할것인지 확실하게 머리에 정리해야한다. 그렇지 않으면 코딩을 하다가 구현의 방향을 바꿔야 하는 경우가 생기고 시간을 엄청 낭비하게 된다. 위 단계를 충실하게 수행했다면 실행결과가 예상과 다르더라도 머리속에 구현에 방향을 확실하게 정리했다면, 디버깅을하는데 시간이 덜 걸릴것이다. 또한 여러 예외사항을 생각할 여유가 생기게 된다.