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

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

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

처음 문제를 풀 때는 왜 bfs로 풀어야하는지 몰라서 일반 구현처럼 요구사항대로 풀었다.

# Try #1
t = int(input())
for _ in range(t):
    n = int(input())
    start = list(map(int, input().split()))
    conv = []
    for _ in range(n):
        conv.append(list(map(int, input().split())))
    conv.sort()
    end = list(map(int, input().split()))
    beer = 20
    
    # 편의점 들리기
    for i in range(n):
        length_x = abs(conv[i][0] - start[0])
        length_y = abs(conv[i][1] - start[1])
        #print(length_x, length_y)
        
        # 편의점 까지 가기
        while length_x > 0:
            beer -= 1
            length_x -= 50
            start[0] += 50
            #print(beer, length_x, start)
        while length_y > 0:
            beer -= 1
            length_y -= 50
            start[1] += 50
        
        # 맥주가 다 떨어지면 종료
        if beer < 0:
            print("sad")
            exit()
        
        # 편의점에 도착했으면 맥주 채우기
        if start[0] >= conv[i][0] and start[1] >= conv[i][1]:
            beer = 20
            continue
    
    # 목적지까지 가기
    length_x = end[0] - start[0]
    length_y = end[1] - start[1]
    
    while length_x > 0:
        beer -= 1
        length_x -= 50
        start[0] += 50
        #print(beer, length_x, start)
    while length_y > 0:
        beer -= 1
        length_y -= 50
        start[1] += 50
    
    if start[0] >= end[0] and start[1] >= end[1] and beer >= 0:
        print("happy")
    else:
        print("sad")

계속 오답이 나와서 찾아보니 BFS로 풀어야하는 문제였다.

 

왜 BFS를 사용해야하냐면, 편의점 좌표는 임의로 주어지기 때문이다.

예를들어, 지도상에 1(시작점) 2(편의점) 3(편의점) 4(편의점) 5(도착지) 순서로 있다고 하자.

편의점 좌표 값이 3 -> 4 -> 2 순서로 들어오게 된다면, 2 -> 5 거리를 맥주가 동나기까지 도착하지 못하게 된다.

 

그렇다면 편의점 좌표 값을 sort하면 되지 않을까? 라는 생각도 했었다.

하지만 좌표계가 직선 좌표계가 아니고 수직 좌표계이므로 x, y 방향 모두를 고려해야 한다.

 

따라서 갈 수 있는 모든 노드를 queue에 추가하고 방문할 수 있는 노드 마다 도착지에 갈 수 있는지 계산하는 BFS를 사용해야했다.

 

이때 "50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다." 요구사항은 노드와 도착지(or 편의점)사이의 x, y 거리의 합이 1000이하인지로 판별했다.

from collections import deque

def bfs(start, visited):
    q = deque()
    q.append(start)
    
    while q:
        x, y = q.popleft()
        # 목적지 도달이 가능한 경우
        if abs(end[0]-x) + abs(end[1]-y) <= 1000:
            print("happy")
            return
        # 목적지 도달이 불가할 경우, 방문 가능한 편의점노드 추가하기
        for i in range(n):
            if abs(conv[i][0]-x) + abs(conv[i][1]-y) <= 1000 and not visited[i]:
                q.append([conv[i][0], conv[i][1]])
                visited[i] = 1
    print("sad")
    return

t = int(input())
for _ in range(t):
    n = int(input())
    start = list(map(int, input().split()))
    conv = []
    for _ in range(n):
        conv.append(list(map(int, input().split())))
    end = list(map(int, input().split()))

    visited = [0]*n
    bfs(start, visited)