[백준/Python] 9205번: 맥주 마시면서 걸어가기

문제 제목이 너무 낭만 넘치네요.

오늘도 최근에 풀던 것과 같이 BFS를 이용한 간단한 문제풀이가 되겠습니다!

제가 제일 좋아하는 맥주입니닿 (출처: google)

-문제

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

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

 

-문제 이해

조건 및 장치들

- 맥주는 총 20병을 가지고 있을 수 있으며 맥주 한 병당 50m를 갈 수 있다. 

    즉, 편의점을 들르지 않고 최대 1000미터를 갈 수 있다.

- 편의점을 들르면 다시 맥주를 리필하기에, 편의점부터 1000미터를 더 갈 수 있다.

- 거리는 맨해튼 거리로 측정한다. 

 

-풀이

방법은 꽤 단순해요.

시작지점부터 상근이가 거쳐가는 모든 지점에서 목표장소까지의 거리가 1000미터를 넘지 않는 곳이 한 곳이라도 있으면

'happy'를 출력해주면 돼요.

 

상근이가 거쳐갈 지점들은 곧 편의점들이 되는 것이고, 입력받는 편의점을 위치를 cvs라는 리스트에 저장해요.

그리고 너비우선탐색을 이용해서 각 편의점에서 이동할 수 있는 다른 편의점을 조사하고 각각의 편의점에서 축제 장소로 갈 수 있는지도 조사해주면 완성이에요!

 

-소스코드

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

def distance(x, x_t, y, y_t):
    return abs(x - x_t) + abs(y - y_t)

def bfs(x, y):
    visited = [0] * c_nums
    coor = deque([(x,y)])
    
    while coor:
        x, y = deque.popleft(coor)
        if distance(x, goal[0], y, goal[1]) <= 1000:
            return 'happy'
            
        for i in range(c_nums):
            if not visited[i] and distance(x, cvs[i][0], y, cvs[i][1]) <= 1000:
                visited[i] = 1
                coor.append((cvs[i][0], cvs[i][1]))
                
    return 'sad'
                
t = int(input())
for _ in range(t):
    c_nums = int(input())
    st = list(map(int, input().split()))
    cvs = [list(map(int, input().split())) for _ in range(c_nums)]
    goal = list(map(int, input().split()))
    
    print(bfs(st[0], st[1]))