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

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

 

사용 알고리즘: bfs 너비우선탐색

 

 

집에서 상근이는 맥주 20개를 가지고 출발

50미터 갈 때마다 맥주를 1개씩 먹으면서 감

편의점에서 살 수 있는 맥주의 최대 개수 20개

 

-> 집에서 출발해서 한번에 갈 수 있는 최대 거리: 50미터 * 20병 = 1000미터

-> 편의점에서 맥주를 샀을 때 한번에 갈 수 있는 최대 거리: 50미터 * 20병 = 1000미터

 

 

1. 상근이의 현재 위치에서 최종 목적지인 락페스티벌의 위치가 1000미터 이내이면 도착 가능

2. 상근이의 현재 위치에서 최종 목적지인 락페스티벌의 위치가 1000미터 보다 멀면 편의점을 들려야 함

3. 편의점을 들리면 맥주를 사고, 상근이 위치를 업데이트 시킴

4. 1 2 3 과정을 반복하여 락페스티벌에 도착할 수 있는지 없는 지 확인

 

import sys
from collections import deque

def bfs():
    queue = deque() # 현재 상근이 위치를 저장할 큐
    queue.append(home)

    while queue:
        x, y = queue.popleft() # 현재 상근이 위치
        
        # (현재위치-락페스티벌위치)의 절댓값이 1000미터 보다 작으면 happy
        if abs(x - rockFestival[0]) + abs(y - rockFestival[1]) <= 1000:
            print('happy')
            return
        # 현재 가지고 있는 맥주량이 부족해 락페스티벌에 갈 수 없음 -> 편의점 들리기
        for i in range(n):
            if visited[i] == 0:
                disX, disY = convenienceList[i]
                # (현재위치-편의점위치) 의 절댓값이 1000보다 작으면 갈 수 있음
                if abs(x - disX) + abs(y - disY) <= 1000:
                    queue.append(convenienceList[i]) # 상근이 위치 업데이트
                    visited[i] = 1 # 방문표시
    print('sad')
    return

# 테스트케이스 갯수
t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline()) # 편의점 갯수
    
    # 초기화
    home = [0, 0]
    convenienceList = [[0, 0] for _ in range(n)]
    rockFestival = [0, 0]

    home[0], home[1] = map(int, sys.stdin.readline().split())
    for i in range(n):
        convenienceList[i][0], convenienceList[i][1] = map(int, sys.stdin.readline().split())
    rockFestival[0], rockFestival[1] = map(int, sys.stdin.readline().split())
    
    # 방문여부확인
    visited = [0 for _ in range(n + 2)]
    
    bfs()