문제 정보
- https://www.acmicpc.net/problem/7187
- BFS, 선분 교차 판정
문제 정리
2차원 얼음판 위에 퍽이 있다. 1초에 한 번 동, 서, 남, 북 중 한 곳에서 퍽을 두드릴 수 있고, 두드리지 않아도 된다. 퍽은 두드린 방향과 반대 방향으로 이동하는 속도가 1 증가하게 되며, 이 속도 값은 최대 7까지만 늘어난다. 두드리지 않을 경우 이전에 이동하는 속도를 유지한다. 또한 얼음판 위에는 선분들이 있는데, 퍽의 이동 경로와 선분들이 부딪히지 않아야 한다. 위 조건을 만족하면서 퍽을 도착 지점까지 이동시킬 때, 걸리는 최소 시간을 구하는 문제이다.
풀이
크게 보면 2차원 얼음판을 격자로 보고, BFS 탐색을 하면서 이동할 때마다 선분 교차 판정을 해주면 된다.
BFS 탐색을 진행할 때, 동, 서, 남, 북 방향으로 때렸을 때와 때리지 않았을 때 총 5가지 상황의 좌표와 속력을 큐에 넣어 탐색해야 한다. 이 경우, 방문 처리 역시 x좌표, y좌표, x좌표의 이동속도, y좌표의 이동속도 총 4개의 값을 관리해 줘야 하므로 4차원 배열이 필요해진다. 물론 이동하는 각 케이스마다 모든 선분과 교차하는지 여부도 체크해줘야 한다.
다음으로 문제가 되는 것은 탐색 좌표의 상한선인데, 속도를 1씩 증가시켜서 속력이 7인 상태로 (3, 10)점에 들어오는 예시를 생각해보면 1+2+3+...+7 = 28에 좌표값 3이니 대충 한계값을 [-40, 40]정도로 잡으면 된다.
대충 이런 느낌
솔브닥 마라톤이 푼사람 3명인 문제를 던져줬다. 그리고 이거 내가 기여하기 전까지 G1이었다...
그와 별개로 좌표 범위를 30까지만 체크했는데 AC가 나왔다. 혹시나 싶어서 +31까지 이동해야 하는 테케를 만들어서 넣어봤는데 AC코드가 잘못된 답을 뱉어냈다. 범위를 40까지 체크하도록 수정했더니 해당 테케에서 올바른 답을 뱉어냈다. 근데 런타임이 1024ms까지 늘어났네?? 아무튼 해당 테케는 질문 게시판에 남겨놨다.
코드
# 백준 7187
import io
from collections import deque
input = io.BufferedReader(io.FileIO(0), 1<<18).readline
addX = [-1, 1, 0, 0, 0]
addY = [0, 0, -1, 1, 0]
MAX_SPEED = 7
BORDER_SPEED = 15
MAX = 30
BORDER = 60
INF = 10**5
# 선분 교차 판정 서브 함수
def CCW(A, B, C):
return (B[0]-A[0]) * (C[1]-A[1]) - (B[1]-A[1]) * (C[0]-A[0])
# 선분 교차 판정
def LineIntersection(A, B, C, D):
AB = CCW(A, B, C) * CCW(A, B, D)
CD = CCW(C, D, A) * CCW(C, D, B)
if AB == 0 and CD == 0:
if B < A:
A, B = B, A
if D < C:
C, D = D, C
return not (B < C or D < A)
return AB <= 0 and CD <= 0
# 선분 AB와 교차하는 다른 선분이 존재하는지 체크
def checkLines(N, lines, A, B):
for i in range(N):
if LineIntersection(A, B, (lines[i][0], lines[i][1]), (lines[i][2], lines[i][3])) == 1:
return True
return False
def BFS(N, lines, endX, endY):
q = deque()
visited = [[[[INF for _ in range(15)] for _ in range(15)] for _ in range(BORDER)] for _ in range(BORDER)]
q.append((MAX, MAX, 0, 0))
visited[MAX][MAX][7][7] = 0
while q:
curY, curX, dy, dx = q.popleft()
if curX == endX and curY == endY:
return visited[endY][endX][dy+7][dx+7]
for i in range(5):
moveX = dx + addX[i]
moveY = dy + addY[i]
nextX = curX + moveX
nextY = curY + moveY
# 좌표 범위 체크 + 이동 속도 체크 + 방문 여부 체크 + 선분 교차 여부 체크
if 0 <= nextX < BORDER and 0 <= nextY < BORDER and -7 <= moveX <= 7 and -7 <= moveY <= 7 and visited[nextY][nextX][moveY+7][moveX+7] == INF and checkLines(N, lines, (curX, curY), (nextX, nextY)) == False:
q.append((nextY, nextX, moveY, moveX))
visited[nextY][nextX][moveY+7][moveX+7] = visited[curY][curX][dy+7][dx+7] + 1
return -1
def main():
endX, endY, N = map(int, input().split())
lines = []
for _ in range(N):
a, b, c, d = map(int, input().split())
lines.append((a+MAX, b+MAX, c+MAX, d+MAX))
print(BFS(N, lines, endX+MAX, endY+MAX))
main()
