[백준] 9205 - 맥주 마시면서 걸어가기 [Python(파이썬)]

문제

www.acmicpc.net/problem/9205

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

 

풀이

문제에 50m, 20병 등과 같은 제약조건들이 덧붙여져 있어 헷갈릴 수 있는 문제였다.

쉽게 말하자면, 편의점 혹은 페스티벌 좌표까지의 거리가 1000m이하여야 한다는 의미였다.

문제 분류는 BFS&플로이드-와샬 알고리즘이었지만, 나는 BFS 개념에 그리디 알고리즘을 적용시켜서 풀어봤다.

 

먼저 시작 좌표를 큐에 담은 뒤, 계속 pop하면서 목적지까지의 거리가 1000m이하인지 체크한다.

만약 목적지까지의 거리가 1000m 이하라면 True를 리턴한다.

아니라면 현재 좌표에서 1000m 이내에 있는 방문하지 않은 편의점의 좌표를 모두 큐에 담아준다.

탐색이 모두 끝나면(큐가 empty한 상태가 되면) False를 리턴한다.

 

 

코드

import sys, collections

def check():
    q = collections.deque([start])
    visited = set()
    while q:
        x, y = q.popleft()
        if abs(x-dst[0]) + abs(y-dst[1]) <= 1000:
            return True
        for i in range(n):
            if i not in visited:
                nx, ny = cos[i]
                if abs(x-nx) + abs(y-ny) <= 1000:
                    q.append([nx, ny])
                    visited.add(i)
    return False
        
t = int(sys.stdin.readline().strip())

for _ in range(t):
    n = int(sys.stdin.readline().strip())
    start = [int(x) for x in sys.stdin.readline().split()]
    cos = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)]
    dst = [int(x) for x in sys.stdin.readline().split()]
    if check():
        print("happy")
    else:
        print("sad")