[백준 1686] 복날 (with Python / BFS)

문제링크

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

1686번: 복날

문제설명

문제

오늘은 복날이다!

해빈이는 복날을 맞아 순살치킨 파티를 하기 위해 닭을 잡으려고 한다. 하지만 이번에도 쉽게 잡힐까보냐. 용감한 닭 한 마리가 해빈이에게서 도망치려 한다. 닭은 v m/sec의 속도로 이동할 수 있고, (xs, ys)에서 (xt, yt)에 존재하는 벙커까지 이동하면 해빈이에게서 도망칠 수 있다. 하지만 닭이 m분 이상 벙커 밖을 돌아다닌다면 바로 해빈이에게 잡혀 치킨이 되고 말 것이다.

과연 닭은 해빈이에게서 도망칠 수 있을까?

입력

첫 번째 줄에는 닭의 속도 v와 생존 가능 시간 m이 주어진다. 두 번째 줄에는 닭의 시작 위치 xs와 ys가 공백을 사이에 두고 주어지며, 세 번째 줄에는 목적지의 위치 xt, yt가 주어진다.

그 다음부터는 중간 지점에 존재하는 벙커들의 좌표 x y가 주어진다.

모든 단위는 m(미터, meter)이다. 중간 지점에 존재하는 벙커들의 개수는 1,000개 이하이고, 모든 좌표의 범위는 -10,000에서 +10,000이다.

출력

만약 닭이 해빈이에게서 도망치는데 성공한다면, 출력은 "Yes, visiting n other holes."이라고 해야 한다(이때 n은 거쳐야 하는 중간 지점 벙커의 최소 개수이다). 한편 닭의 미래가 처참하다면 "No."를 출력하면 된다.

예제 입력 1 복사

3 1
0.000 0.000
500.000 0.000
179.000 0.000
358.000 0.000

예제 출력 1 복사

Yes, visiting 2 other holes.

 

문제풀이

어려웠다.

평면에서 두점 사이 거리 공식으로 조건 검사 하는 것 까지는 인지하였으나,

처음에 입력될 벙커 개수를 알려주지 않아, EOF 에러 처리 하는 것을 구현했다.

 

핵심은 BFS를 활용하는 거다.

BFS시,

노드 방문 조건문에 방문체킹하는 로직 구현 안해서 메모리 초과 나기도 했으므로 꼭 체킹하자.

 

핵심

1. v * m * 60 이상 이동하면 안됨.(조건문 처리) 벙커를 통과하면서 가는 것을 구현

2. 벙커좌표 따로 리스트에 담아두기. BFS시 전부 탐색해야하므로 bunker 리스트 전체 돌려서 조건문 검사할것

   cf. 조건문: 방문 여부 / 범위내로 이동가능한지

3. 방문체크하는 배열 따로 만들어서 방문처리하고 조건문에도 방문여부 체킹.

 

코드

import math
from collections import deque

v, m = map(float, input().split())
xs, ys = map(float, input().split())
xt, yt = map(float, input().split())
bunker = []
cnt = 0 
maxRange = v * m * 60
result = False
visited = []

# 벙커 개수 안알려주는듯?
# EOF Error 잡기
while True:
    try:
        data = input()
        if not data:
            break
        x, y = map(float, data.split())
        bunker.append((x, y))    
    except:
        break
    

def calculateDist(a, b, x, y):
    return math.sqrt((x-a)**2 + (y-b)**2)

def BFS(xs, ys):
    global cnt, result
    queue = deque([(xs, ys, cnt)])
  
    while queue:
        curX, curY, cnt = queue.popleft()

        if calculateDist(curX, curY, xt, yt) < maxRange:
            result = True
            return result

        for item in bunker:
            xm, ym = item
            if item not in visited and calculateDist(curX, curY, xm, ym) < maxRange:
                queue.append((xm, ym, cnt+1))
                visited.append(item)

    return result

if BFS(xs, ys):
    print(f"Yes, visiting {cnt} other holes.")
else:
    print('No.')


# 이동하는 거리 구하기 (x, y) (a, b) 
# 평면에서의 두 점 사이 거리 = (a-x)**2 + (b-y)**2 

# 3 m/s 속도인데 제한시간 60s 안이면
# 179m 이상 갈 수 없다.