[모각코] 210825 Today I Learned

<문제 9205번 - 맥주 마시면서 걸어가기>

 

문제를 처음 봤을 때 이해가 가지 않아서 무슨 말인지 한참을 읽었다.

우선 50m마다 맥주를 마셔야 하고, 맥주는 20개 씩 들고 갈 수 있다는 말이 노드와 노드 사이의 거리가 1000m가 넘어서는 안된다는 뜻임을 캐치해야 했다.

그 후에는... 누가누가 코드로 잘 만들어내느냐....

dxdy기법 안 쓴 bfs 문제 오랜만이라 재밌고.. 어려웠다.

 

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()

 

 

---

조금 더 자세한 설명

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