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

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

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

맥주 마시면서 걸어가기 문제

맥주를 마시면서 1000m를 갈 수 있는지 체크하면서 최종적으로 축제까지 갈 수 있는지 확인하는 문제

 

#사용 알고리즘

너비 우선 탐색

📌문제 접근 포인트

1. 각각의 집, 편의점(n개), 축제장 위치의 정보를 입력받고, 갈 수 있는지 체크해보자. 맥주 20개를 사서 50m당 1개씩 먹을 수 있으므로, 최대 1000m 까지 이동할 수 있다는 점을 이용해보자.

2. 거리를 체크해야 하므로 너비 우선 탐색을 활용해보자. 각각 방문 여부를 체크해가면서, 조건에 맞는지 체크하자. 결국에 큐에서 꺼낸 위치와 축제장의 위치까지 맨해튼 거리로 1000m 이하로 1번이라도 존재하면, 축제장에 도착 할 수 있는거니 happy를 반환해주자.

3. 다 돌았음에도 happy를 반환하지 못하면, 결국 도착을 못한다는 이야기니 sad를 반환하도록 구성해주면 성공

⚙ 내가 푼 정답 코드

def find():
    queue = deque([[homey, homex]])
    while queue:
        y, x = queue.popleft()
        if abs(y-festy) + abs(x-festx) <= 1000: # 축제장에 도착할 수 있으면
            return "happy" # 성공
        for i in range(n):
            if not visited[i]:
                ny, nx = Songdo[i]
                if abs(y - ny) + abs(x - nx) <= 1000: # 다음 편의점까지 1000m 이하면
                    visited[i] = 1 # 방문하고
                    queue.append([ny,nx]) # 다시 출발
    return "sad" # 다 돌았음에도 반환 못하므로 sad

import sys
from collections import deque
T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    homey, homex = map(int, sys.stdin.readline().split())
    Songdo = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    festy, festx = map(int, sys.stdin.readline().split())
    visited = [0]*(n+1)
    print(find())