[백준] 10875 뱀, python

https://www.acmicpc.net/problem/10875

 

 

 

 

 

주어진 명령에 따라 뱀이 몸을 늘려나가는데 도중에 격자판을 벗어나거나 자신의 몸통에 닿을 때까지의 시간을 구하는 문제이다.

 

격자판의 크기가 최대 \(10^{8}\) 이고 t가  최대 \(2\cdot10^{8}\) 이므로 격자판을 2차원 배열로 만들고, 1초마다 머리를 갱신해서 풀게 되면 메모리와 시간초과가 나게 된다.

 

따라서 뱀이 직선으로 이동했을때 늘려진 몸통을 선분으로 저장하게 되면, 선분이 교차되면 머리가 몸통에 닿은 것이라고 할 수 있다.

교차되지 않았다면 t만큼 추가해주고, 교차되었다면 교차된 선분 중에 현재 선분의 시작점과 교점까지의 거리가 최소인 시점에 종료해주면된다.

 

 

선분이 교차하지 않으면 몸통에 계속 추가해 나가고, 만약 교차한다면 교점들을 전부 구한다.

구한 교점 중에 시작점과 가장 가까운 교점까지의 거리만큼 이동해 주고 종료하면 된다.

 

두 선분의 교차 판정(1), python

두 선분의 교차 판정(1), python

 

두 선분의 교점은 매개변수 방정식을 통해 구해주었다.

 

격자판 외부로 벗어나는 걸 체크하기 위해 격자 테두리에도 선분을 추가하여 몸통 교차와 동일하게 처리해 주었다.

 

모든 명령어를 수행한 이후에도 종료되지 않았다면 격자판에서 벗어날 때까지 계속 몸을 늘려줘야 한다. 

 

 

from collections import*
import sys
input = sys.stdin.readline

L=int(input())
N=int(input())
cmd = []
for _ in range(N):
    t,dir = input().split()
    cmd.append((int(t),dir))
# 명령이 끝난 이후에도 계속 이동
cmd.append((10**9,'L'))

dx = [1,0,-1,0]
dy = [0,1,0,-1]
# 격자판 테두리에 선분 추가
body = [
    (L+1,L+1,L+1,-L-1),
    (L+1,L+1,-L-1,L+1),
    (-L-1,-L-1,L+1,-L-1),
    (-L-1,-L-1,-L-1,L+1)
]

# 선분 교차 검증, 만약 교차한다면 교차한 점의 좌표를 반환, 교차하지 않는다면 빈 배열 반환
def cross(p1,p2,p3,p4):
    x1,y1=p1; x2,y2=p2
    x3,y3=p3; x4,y4=p4
    a = x2-x1; b = x3-x4; e = x3 -x1
    c = y2-y1; d = y3-y4; f = y3 -y1

    if a*d-b*c==0:
        if d*e-b*f==0:
            if max(min(p1,p2),min(p3,p4))==min(max(p1,p2),max(p3,p4)):
                return [max(min(p1,p2),min(p3,p4))]
            elif max(min(p1,p2),min(p3,p4))<min(max(p1,p2),max(p3,p4)):
                return [max(min(p1,p2),min(p3,p4)),min(max(p1,p2),max(p3,p4))]
        return False
    else:
        s = (d*e-b*f)/(a*d-b*c)
        t = (a*f-c*e)/(a*d-b*c)
        if 0<=s<=1 and 0<=t<=1:
            x = x1+s*(x2-x1)
            y = y1+s*(y2-y1)
            return [(int(x),int(y))]
        else:
            return False

# 움직일수 있는지 여부와 시간을 반환
# 교점이 있다면 가장 가까운 교점까지의 거리를 구함
def moveable(x1,y1,x2,y2,t):
    points = []
    print(body[:-1])
    for x3,y3,x4,y4 in body[:-1]:
        p = cross((x1,y1),(x2,y2),(x3,y3),(x4,y4))
        if p:
            for x in p:
                points.append(x)

    if not points:
        return (True,t)
    else:
        d = 10**16
        for x,y in points:
            d = min(d,abs(x-x1)+abs(y-y1))
        return (False,d)


answer = 0
cur_dir = 0
cx,cy=0,0

# 움직일 수 없을때까지 시간을 더해줌
for t,dir in cmd:
    nx,ny = cx+t*dx[cur_dir], cy+t*dy[cur_dir]
    cur_dir = (cur_dir+1)%4 if dir=='L' else (cur_dir+3)%4

    valid, moves = moveable(cx,cy,nx,ny,t)
    answer += moves
    
    if not valid:
        break
    
    body.append((cx,cy,nx,ny))
    cx,cy = nx,ny

print(answer)