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

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

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

 

내 코드

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

def bfs():
    q = deque()
    q.append((hx, hy))
    while q:
        x, y = q.popleft()
        if abs(x - fx) + abs(y - fy) <= 1000:
            print('happy')
            return
        
        for i in range(n):
            if not visited[i]:
                nx, ny = conv[i] #편의점만 집중적으로 보기
                if abs(x-nx) + abs(y-ny) <=1000:
                    visited[i] =1
                    q.append((nx, ny))
    print('sad')
    return

t= int(input())
for _ in range(t):
    conv = []
    n = int(input())
    hx, hy = map(int, input().split())
    for _ in range(n):
        cx, cy = map(int, input().split())
        conv.append((cx, cy))
    fx, fy = map(int, input().split())
    visited = [0 for _ in range(n+1)]    
    bfs()

 

코드 리뷰

BFS

해당 문제는 일반적인 BFS 문제에 경유지가 생긴 문제이다. 

반드시 경유해야 하는 조건이 추가되었으며, 경유하는 것이 가능한 상황이 주어진다.

박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

알콜 중독이,, 알콜이 다 떨어지기 전에는 편의점을 한 번은 들르면서 목적지까지 도착해야 한다는 것이다.

for _ in range(t):
    conv = []
    n = int(input())
    hx, hy = map(int, input().split())
    for _ in range(n):
        cx, cy = map(int, input().split())
        conv.append((cx, cy))
    fx, fy = map(int, input().split())
    visited = [0 for _ in range(n+1)]

이렇게 기본적인 세팅을 해준다. 기본적으로 연산에 필요한 배열들을 다 초기화해준다. 그리고 hx, hy는 집 좌표, cx, cy는 편의점 좌표, fx, fy는 페스티벌 좌표로 설정한다.

def bfs():
    q = deque()
    q.append((hx, hy))
    while q:
        x, y = q.popleft()
        if abs(x - fx) + abs(y - fy) <= 1000:
            print('happy')
            return
        
        for i in range(n):
            if not visited[i]:
                nx, ny = conv[i] #편의점만 집중적으로 보기
                if abs(x-nx) + abs(y-ny) <=1000:
                    visited[i] =1
                    q.append((nx, ny))
    print('sad')
    return

그리고 초기 좌표는 집 좌표로 설정한다. 일반적인 bfs 와 마찬가지로 진행하지만, 조건이 하나 추가되었다.

q에 수가 존재하는 동안, 현재 좌표(편의점 좌표 중 하나)에서 1000이 넘지 않은 거리에서 페스티벌 좌표(목적지)를 발견했을 때 happy를 출력하는 것이다.

이 코드는 주어진 편의점 좌표만을 경유하면서 계산이 진행된다.

• 해당 편의점은 아직 방문하지 않아야 한다.
• 편의점끼리의 거리 차이는 1000이상이 나면 안된다.
• 페스티벌 장소와 마지막(이 아니어도 됨) 편의점까지의 거리 차이도 1000 이상이 나면 안된다.

위의 코드는 이 모든 조건을 부합하는 코드이다.

그리고 만약 q를 다 돌았는데도 불구하고 조건에 부합하는 편의점 좌표가 존재하지 않았다면 sad를 출력한다.