[Python] 백준 9205번 - 맥주 마시면서 걸어가기

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

9205번: 맥주 마시면서 걸어가기

 

박스에 맥주를 최대 20개 까지 담을 수 있고, 50m에 맥주 한 병씩을 마셔야 한다.

=> 노드들 간의 거리가 1000m를 넘어서는 안 된다.

 

문제가 복잡해보이게 적혀있어서 그렇지 이것만 이해하면 나름 괜찮았던 것 같다.

 

입력 받는 부분에서 1차로 막혔었는데 편의점이 n개라서 for문을 n+2로 돌려서 입력값 전체를 다 받으려고 했었다.

다시 보니까 편의점 n개만 for문으로 돌리고 집이랑 페스티벌은 따로 입력을 받는 게 편할 것 같아서 수정하였다.

 

bfs는 대부분 dxdy 기법 문제를 풀었어서 그런지 이것도 dxdy로 풀어야되나? 라는 생각을 했었다.

제발.. 넓은 시야를 갖자. 너무 단순하게 생각하지 마시오..

 

for문을 돌려서 노드들 간의 거리를 확인하여 1000m가 넘지 않는 경우 append를 하여 진행하는 방식을 사용했다.

목적지인 락 페스티벌(fest)에 도착하는 경우 happy, 도착하지 못하는 경우 sad를 출력해야 하므로 그 부분에 해당하는 조건문도 따로 넣어주었다.

 

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

def bfs():
    q = deque()
    q.append([home[0], home[1]])
    while q:
        x, y = q.popleft()
        if abs(x - fest[0]) + abs(y - fest[1]) <= 1000:
            print("happy")
            return
        for i in range(n):
            if not visited[i]:
                new_x, new_y = conv[i]
                if abs(x - new_x) + abs(y - new_y) <= 1000:
                    q.append([new_x, new_y])
                    visited[i] = 1
    print("sad")
    return

t = int(input())
for i in range(t):
    n = int(input())
    home = [int(x) for x in input().split()]
    conv = []
    for j in range(n):
        x, y = map(int, input().split())
        conv.append([x, y])
    fest = [int(x) for x in input().split()]
    visited = [0 for i in range(n+1)] #home 제외
    bfs()