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

Song_MinGyu·2023년 1월 3일

BFS/DFS Graph boj python

Algorithm

목록 보기

26/30

백준 9205 - 맥주 마시면서 걸어가기

문제

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

풀이

풀이 키워드

맥주 마시면서 걸어가기에서 문제를 풀이하는데 확인해야할 키워드는 아래와 같다.

맥주 한박스를 가지고 있다 => 시작할 때 20의 수를 가지고 있다.
50미터마다 맥주 한병씩 마셔야하고, 가지고있는 맥주를 다 마실경우 목적지에 도달 할 수 없다. => 한번에 최대 1000미터까지 이동 할 수 있다.
편의점에 들리면 맥주를 최대 20병까지 다시 채울 수 있다.
입력은 시작 좌표, 편의점 좌표, 목적지 좌표로 이루어져있다.
출력은 도달할 수 있는지/없는지만 판단하면 된다.

시도한 방법 1)

오래 전 처음 시도한 방법에는 해당 방법이 그래프를 이용한 방법인지 모르고 그리디하게 문제를 풀어보려고 했다.

from collections import deque

T = int(input())
for i in range(T):
    sad_counter = True
    combine = []
    n = int(input())
    home = list(map(int,input().split()))
    for i in range(n):
        combine.append(list(map(int,input().split())))
    combine = deque(combine)
    rock = list(map(int,input().split()))


    while combine:
        tmp_combine = combine.popleft()
        tmp_manhaten = abs(tmp_combine[0]-home[0]) + abs(tmp_combine[1]-home[1])
        if tmp_manhaten//50 > 20:
            sad_counter = False
            print('sad')
            break
        home = tmp_combine
    tmp_rock = abs(rock[0]-home[0]) + abs(rock[1]-home[1])
    if tmp_rock//50 > 20 and sad_counter == True:
        print('sad')
        continue
    elif sad_counter == True:
        print('happy')

당연히 틀렸다

시도한 방법 2)

그 다음으로 시도한 방법은 BFS 방법을 이용하여 50미터마다 좌표를 이동, 그리고 이동할 때 마다 맥주를 하나씩 제거하는 방법을 이용했다.

import sys
from collections import deque

def bfs(start_x:int,start_y:int,target_x:int,target_y:int,combin:list):
    checker = deque()
    que = deque()
    checker.append([start_y,start_x])
    que.append([start_y,start_x,20])
    dx = [0,0,50,-50]
    dy = [50,-50,0,0]
    while que:
        cx,cy,beer = que.popleft()
        if cx == target_x and cy == target_y:
            return "happy"
        if [cx,cy] in combin:
            beer = 20
        if beer == 0:
            continue
        beer -= 1
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if not [nx,ny] in checker and -32768 <= nx <= 32767 and -32768 <= ny <= 32767:
                que.append([nx,ny,beer])
                checker.append([nx,ny])
    return "sad"

for tc in range(int(sys.stdin.readline())):
    combine = []
    n = int(sys.stdin.readline())
    sx,sy = map(int,sys.stdin.readline().split())
    for i in range(n):
        combine.append(list(map(int,sys.stdin.readline().split())))
    tx,ty = map(int,sys.stdin.readline().split())
    print(bfs(sx,sy,tx,ty,combine))

이 방법을 사용할 때 일반적인 방문 확인을 할 수 없어 리스트에 지속적으로 추가하고 그 값들을 확인하는 방법을 이용했다. 아마도 이 방법이 정답을 낼 수 있어도 시간관리에서 상당히 불리했을 것으로 예상한다.

정답인 방법

정답인 방법은 맥주 1개당 50미터를 이동할 수 있고, 20개를 들고있으므로 맥주 한박스당 1000미터를 이동할 수 있다는 점을 이용하여 문제에 접근한다.
만약 처음 맥주 20개를 들고 있는데 이동거리가 1000미터 이내에 편의점도 없고, 목적지도 없다면 맥주 20개를 들고 이동하는 것은 불가능하다.
그렇다면 맥주 20개를 들고 있고 1000미터 이내에 편의점이 있다면? 편의점으로 가서 다시 맥주 20개를 채울 수 있다. 그리고 해당 지점에서 다시 1000미터 이내에 목적지나 편의점이 있는지 파악하면 된다.
그리고 1000미터 이내에 목적지가 있다면? 편의점을 들리지 않고도 목적지에 도달하는 것이 가능하다.
이 방법들을 이용하여 BFS 방법을 사용하면 된다.

import sys
from collections import deque

def bfs(start_x:int,start_y:int,target_x:int,target_y:int,combin:list):
    checker = deque()
    que = deque()
    checker.append([start_x,start_y])
    que.append([start_x,start_y])
    while que:
        cx,cy = que.popleft()
        if abs(cx-target_x) + abs(cy-target_y) <= 1000:
            return "happy"
        for i in range(len(combin)):
            if not [combin[i][0],combin[i][1]] in checker and abs(cx-combin[i][0]) + abs(cy-combin[i][1]) <= 1000:
                checker.append([combin[i][0],combin[i][1]])
                que.append([combin[i][0],combin[i][1]])
    return "sad"


for tc in range(int(sys.stdin.readline())):
    combine = []
    n = int(sys.stdin.readline())
    sx,sy = map(int,sys.stdin.readline().split())
    for i in range(n):
        combine.append(list(map(int,sys.stdin.readline().split())))
    tx,ty = map(int,sys.stdin.readline().split())
    print(bfs(sx,sy,tx,ty,combine))