반응형
1. 풀이
처음에는 격자를 이용해서 풀려고 했다. (소스코드1)
0.5초 만에 만나는것을 구현하기 힘들어서 최대범위는 +-2000으로 했고, (x,y)를 (r,c)로 바꿔주기위해
r=2*x+2000, c=2*y+2000으로 하여 4000*4000의 격자를 만들어준 후 문제를 풀었다.
하지만 이 방법으로는 메모리 초과가 났다.
따라서 아래와 같이 격자를 쓰지 않는 방법으로 문제를 풀었다.
(1) atomD에 현재 원자들의 상태와 상태를 저장한다
(2) 이동시킨다
- 범위 밖이면 삭제한다 (이동할 때 원자가 범위 밖에서 만나는 경우는 없으므로)
- 범위 안이면 cheakD에 저장하고, 바뀐 위치를 새롭게 atomD에 저장한다
(이때 cheakD는 dictionary형태로, key값을 (행,열)과 같은 튜플형태로 하는 갖는 자료형이다.)
(3) cheakD를 전부 조사하여 해당 위치에 두개이상의 원자가 있으면 atomD를 삭제한다.
※시간 초과가 날것을 걱정해서 격자를 사용했지만, 격자때문에 메모리 초과가 났다. 격자를 이용하면 해당위치를 즉시 확인할 수 있기 때문에 속도는 빠르지만 메모리가 초과할 수 있다는 트레이드 오프가 있다. 이를 정확히 인지하고 무조건 격자를 사용하지 않도록 주의한다.
시간복잡도는
원자가 한쪽구석에서 반대쪽 구석으로 가는 경우(4000)*원자의 최대개수(1000)=O(4000*1000)이므로 충분히 해결할 수 있다.
2. 소스코드
(1) 소스코드1 (격자, 메모리초과)
from collections import deque
T=int(input())
dR=[0,0,-1,1]
dC=[1,-1,0,0]
for t in range(T):
N=int(input())
# L[r][c]=[i,d,k] i번쨰 원자가 d방향으로이동중, 에너지는 k.
L=[[[] for j in range(4001)] for i in range(4001)]
atomD=deque([])
for i in range(N):
x,y,d,k=map(int,input().split())
r=2*x+2000
c=2*y+2000
L[r][c].append(i)
atomD.append([i,r,c,d,k])
ans=0
while(atomD):
size=len(atomD)
#원자 움직이기
for _ in range(size):
#원래있던곳 삭제
atomNum,r,c,d,k=atomD.popleft()
L[r][c].remove(atomNum)
#새로갈곳 찾아서 옮기기
tempR = r + dR[d]
tempC = c + dC[d]
if 0<=tempR<4001 and 0<=tempC<4001:
L[tempR][tempC].append(atomNum)
atomD.append([atomNum,tempR,tempC,d,k])
#부딪힌곳 있는지 확인
delL=[]
for atomNum,r,c,d,k in atomD:
if len(L[r][c])>=2:
delL.append([atomNum,r,c,d,k])
#부딪힌곳 삭제
for atomNum,r,c,d,k in delL:
atomD.remove([atomNum,r,c,d,k])
L[r][c].remove(atomNum)
ans+=k
print("#%d %d"%(t+1,ans))
(2) 소스코드2 (통과)
from collections import deque
T=int(input())
dR=[0,0,-1,1]
dC=[1,-1,0,0]
for t in range(T):
N=int(input())
atomD=deque([])D
for i in range(N):
x,y,d,k=map(int,input().split())
r=2*x+2000
c=2*y+2000
atomD.append([i,r,c,d,k])
ans=0
while(atomD):
cheakD={}
size=len(atomD)
#원자 움직이기
for _ in range(size):
#원래있던곳 삭제
atomNum,r,c,d,k=atomD.popleft()
#새로갈곳 찾아서 옮기기
tempR = r + dR[d]
tempC = c + dC[d]
if 0<=tempR<4001 and 0<=tempC<4001:
atomD.append([atomNum,tempR,tempC,d,k])
if (tempR,tempC) in cheakD:
cheakD[(tempR,tempC)].append([atomNum,d,k])
else:
cheakD[(tempR,tempC)]=[[atomNum,d,k]]
#부딪힌곳 있는지 확인
for tup in cheakD:
if len(cheakD[tup])>=2:
for atomNum,d,k in cheakD[tup]:
atomD.remove([atomNum,tup[0],tup[1],d,k])
ans+=k
print("#%d %d"%(t+1,ans))
반응형