문제 링크
https://www.acmicpc.net/problem/10875
🕒 Python 풀이시간: x
dx=[-1,0,1,0]
dy=[0,1,0,-1]
x,y,d=0,0,1
l=int(input())
n=int(input())
opers=[list(input().split()) for _ in range(n)]
totalT=0
traces=[]
def isCrushed(tx1,ty1,tx2,ty2,x1,y1,x2,y2):
if tx1>tx2 and ty1==ty2:
if y1==y2 and y1==ty1:
if tx1>=x1>=tx2 or tx1>x2>tx2:
return True
elif x1==x2 and y1>y2:
if y1>=ty1>=y2 and tx1>=x1>=tx2:
return True
elif x1==x2 and y1<y2:
if y2>=ty1>=y1 and tx1>=x1>=tx2:
return True
elif tx1<tx2 and ty1==ty2:
if y1==y2 and y1==ty1:
if tx1<=x1<=tx2 or tx1<=x2<=tx2:
return True
elif x1==x2 and y1>y2:
if y1>=ty1>=y2 and tx2>=x1>=tx1:
return True
elif x1==x2 and y1<y2:
if y2>=ty1>=y1 and tx2>=x1>=tx1:
return True
elif tx1==tx2 and ty1>ty2:
if x1>x2 and y1==y2:
if x1>=tx1>=x2 and ty1>=y1>=ty2:
return True
elif x1<x2 and y1==y2:
if x2>=tx1>=x1 and ty1>=y1>=ty2:
return True
elif x1==x2 and x1==tx1:
if ty1>=y1>=ty2 or ty1>=y2>=ty2:
return True
elif tx1==tx2 and ty1<ty2:
if x1>x2 and y1==y2:
if x1>=tx1>=x2 and ty2>=y1>=ty1:
return True
elif x1<x2 and y1==y2:
if x2>=tx1>=x1 and ty2>=y1>=ty1:
return True
elif x1==x2 and x1==tx1:
if ty1<=y1<=ty2 or ty1<=y2<=ty2:
return True
return False
allClear=False
for i in range(n):
t,dir=int(opers[i][0]),opers[i][1]
nx=x+dx[d]*t
ny=y+dy[d]*t
checked=False
dist=1e9
for x1,y1,x2,y2 in traces:
if isCrushed(x1,y1,x2,y2,x+dx[d],y+dy[d],nx,ny):
if d==0 or d==2:
dist=min(dist,abs(x-x1))
else:
dist=min(dist,abs(y-y1))
checked=True
if checked:
totalT+=dist
allClear=True
break
if nx<-l or ny<-l or nx>l or ny>l:
dist=0
if d==0:
dist=abs(-l-x)
if d==1:
dist=abs(l-y)
if d==2:
dist=abs(l-x)
if d==3:
dist=abs(-l-y)
totalT+=dist+1
allClear=True
break
traces.append((x,y,nx,ny))
x,y=nx,ny
if dir=='L':
d=(d+1)%4
else:
d=(d-1)%4
totalT+=t
if allClear:
print(totalT)
else:
checked=False
dist=1e9
nx,ny=x,y
if d==0:
nx=-l
elif d==1:
ny=l
elif d==2:
nx=l
elif d==3:
ny=-l
for x1,y1,x2,y2 in traces:
if isCrushed(x1,y1,x2,y2,x+dx[d],y+dy[d],nx,ny):
if d==0 or d==2:
dist=min(dist,abs(x-x1))
else:
dist=min(dist,abs(y-y1))
checked=True
if checked:
totalT+=dist
allClear=True
print(totalT)
else:
dist=0
if d==0:
dist=abs(-l-x)
if d==1:
dist=abs(l-y)
if d==2:
dist=abs(l-x)
if d==3:
dist=abs(-l-y)
totalT+=dist+1
print(totalT)뱀 게임 시뮬레이션 문제! 🐍⏳
뱀이 시간에 따라 몸 길이를 늘려가며 진행할 때, 벽이나 몸에 부딪치면 종료하는 문제이다. 단순히 시간에 따라 뱀의 움직임을 늘리고 싶으나 전체 보드의 크기가 약 2억x2억이 나올 수 있기에 이는 불가능하고 다른 방법을 써야한다.
두가지 조건만 찾아나가면 되는데 뱀이 자신의 몸에 충돌했을 경우, 벽에 충돌했을 경우이다. 시간에 따라 뱀의 몸을 전부 기록할 수 없기에 단순히 방향을 바꿀 때마다 꺾이는 좌표를 가지고 간다. 즉 현재로 부터의 시작 지점과 꺾일 때의 지점을 꺾일 때마다 기록하는 것이다. 그렇게 된다면 시간복잡도 상으로 N개만 기록하면 되므로 현재와 몸의 충돌을 확인할 때도, NxN이기에 1,000,000만에 가능하다.
몸과의 충돌조건은 간단히 전부 비교대조하면된다. 좌표의 위치를 기반으로 언제 두 선분이 교차하는지만 구하면 되기 때문이다. 이 때 선분의 수직으로 교차할 때뿐만 아니라 수평으로 교차할 때도 고려하면 된다. 그리고 비교할 때, 바로 몸의 충돌 지점을 찾자마자 값을 더해주는 것이 아닌 가장 가깝게 충돌한 지점을 구해야 우리는 시간을 계산할 수 있으므로 모든 몸의 구역을 확인한 후, 가장 최근에 충돌한 시간을 구해서 답에 더해주어야 한다.
이후에는 벽과의 충돌을 계산하면 되는데 이 때, 문제의 x,y 좌표값과 그림이 보통 쓰는 좌표값과 달라서 헷갈려서 애먹었다. 충돌하게 된다면, 즉 다음 좌표 값이 벗어나게 된다면 현재 방향을 기준으로 삼아서 벽까지의 거리를 더해주면 된다. 이 때, 벽 앞의 좌표가 아닌 벽과 만나고 그 다음 좌표인 것을(즉, 충돌하고 나서 인 것) 확인하면 된다.
이제 주어진 꺾일 때의 방향값을 처리했으니 비슷한 처리를 한 번 더 해주면 된다. 만약 모든 명령이 수행되고도 아직도 충돌을 안했다면 계속해서 진행해야하기 때문이다. 이 때에도 다시 몸에 부딪치거나 벽에 부딪칠 수 있기 때문에 이 거리를 똑같이 구해서 시간에 더해주면 된다.
이렇게 Python으로 백준의 "뱀" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
