백준 9205 문제 풀이

🐒 맥주 마시면서 걸어가기

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

✍ 나의 풀이

import sys
from collections import deque

input = sys.stdin.readline


t = int(input())
for _ in range(t):
    ways = []

    n = int(input())
    visited = [False] * (n+1)

    a,b = map(int, input().split())
    now = (a,b)

    for _ in range(n):
        a, b = map(int,input().split())
        ways.append((a,b))
    a, b = map(int,input().split())
    ways.append((a,b))
    goal = (a,b)

    def search(now):
        q = deque()
        q.append(now)
        while q:
            x0, y0 = q.popleft()
            for i in range(n+1):
                if not visited[i]:
                    x1,y1 = ways[i]
                    if abs(x0-x1) + abs(y0-y1) <= 1000:
                        visited[i] = True
                        q.append((x1,y1))
                        if (x1,y1) == goal:
                            return 'happy'
        return 'sad'
    
    print(search(now))

문제 지문을 제대로 안읽어서 2트만에 통과했다
원통하다 😢

---

🧠 문제 이해

집에서 맥주 한박스 (20병)을 가지고 50m를 이동할때마다 한병씩 까마신다.
맥주가 떨어지면 이동할 수 없다.
편의점에 들러서 맥주 한박스를 채워 나올 수 있다.

따라서 집에서 나오거나 편의점에 들릴때마다 1000m까지 이동할 수 있다.

그렇게 페스티벌 장소까지 이동한다.

그래서 나는 편의점들의 위치를 받아서, 현재위치에서 편의점들이나 도착지가 1000m 이내라면 그곳으로 이동한다. 이동한 편의점은 방문처리를 하고 현재위치를 업데이트 한다. 현재위치가 도착지라면 happy를 출력하고, 갈 곳이 더이상 없다면 sad를 출력한다.

---

조건에 -32768 ≤ x, y ≤ 32767 이므로
좌표가 대략 4,295,491,600 개 이므로 전체 좌표를 인접행렬로 나타내어 하나씩 탐색하면 시간초과에 걸릴것이다.

또한 문제에서 거리를 구하는 식이 수학시간에 좌표평면에서 배운 좌표간의 거리와 다르다.

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

이게 무슨 소리인지 몰라서 처음에 답을 못 맞췄다.

여튼 대각선 거리를 구하는게 아니다..

if int(((abs(x0-x1))**2 + (abs(y0-y1))**2)**(1/2)) <= 1000:

을

if abs(x0-x1) + abs(y0-y1) <= 1000:

로 바꾸니 바로 풀렸다.

코드가 많이 더러워 보이는데 리팩토링이 필요할 것같다.

문제 지문을 꼼꼼히 읽자~