[백준✨] 9205번 <맥주 마시며 걸어가기> / Python 문제풀이 /

해답)

from collections import deque
import sys

def input():
    return sys.stdin.readline().rstrip()

def calDisatance(p1, p2): # 거리 계산 함수
    x1, y1 = p1
    x2, y2 = p2
    return abs(x1-x2) + abs(y1-y2)

t = int(input())

for _ in range(t): # 테스트 케이스만큼 반복
    CUs = [] # 편의점들

    # 입력받기
    n = int(input())
    home_x, home_y = map(int, input().split())
    home = (home_x, home_y)
    for _ in range(n):
        CU_x, CU_y = map(int, input().split())
        CUs.append((CU_x, CU_y))
    dest_x, dest_y = map(int, input().split())
    dest = (dest_x, dest_y)

    '''
    BFS 로 도착 가능한지 탐색
    현재 도착 가능하면 result 를 'happy' 로 바꾸고 루프탈출 
    도착 불가능하다면, 갈 수 있는 편의점을 찾아서 큐에 넣는다.
    '''
    visited = [False for _ in range(len(CUs))]
    result = "sad"
    q = deque([home])
    while q:
        now = q.popleft()
        if calDisatance(now, dest) <= 1000:
            result = "happy"
            break
        for i in range(len(CUs)):
            if visited[i] or calDisatance(now, CUs[i]) > 1000:
                continue
            q.append(CUs[i])
            visited[i] = True    
    # 결과 출력
    print(result)

---

풀이)

테스트 케이스 t 가 최대 50 밖에 안되고,  편의점 개수 n 도 최대 100 이내이므로

시간 복잡도 신경을 크게 안써도 된다!

 

=> BFS 를 이용해서 현재 들릴 수 있는 곳들을 가면서, 목적지에 도착가능하면 Break 하도록 짰다.

- 플로이드-워셜 이나 다른 방법을 써도 풀릴 것 같다 ! 😉

 

* 추가적인 설명은 코드내에 주석으로

 

 

 

 

* 위 문제의 저작권은 백준(https://www.acmicpc.net/) 에 있습니다.