[python] 백준 9205 맥주 마시면서 걸어가기

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

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

 

문제 해결

• 집(home)에서 목적지(end) 까지 도달 할 수 있는지 문제
• 중간 편의점(conv)은 지나도 되고 안지나도 된다.
• 50갈 때 마다 맥주 하나씩 없어지므로 목적지(end)까지 거리가 1000이하가 되는지 현재 위치에서 거리가 1000이하인 편의점을 하나씩 가보면서 확인
• 편의점을 하나씩 가보는 것은 bfs로 이동하는 것이 편하다.
• 만약 편의점을 다 돌면서 목적지(end)까지 거리가 1000이하가 되는 지점이 없으면 sad를 출력

 

CODE

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

def bfs():
    que = deque()
    que.append(home)
    while que:
        x, y = que.popleft()
        if abs(x-end[0]) + abs(y-end[1]) <= 1000:
            print("happy")
            return
        for i in range(n):
            if visited[i] == False:
                new_x, new_y = conv[i]
                if abs(x-new_x) + abs(y-new_y) <= 1000:
                    que.append(conv[i])
                    visited[i] = True
    print('sad')
    return
for _ in range(int(input())):
    n = int(input())
    home = list(map(int, input().split()))
    conv = [list(map(int, input().split())) for _ in range(n)]
    end = list(map(int,input().split()))
    visited = [False for _ in range(n+2)]
    bfs()