[백준/파이썬] 9205 : 맥주마시면서 걸어가기

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

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

문제 요약 : 상근이와 친구들은 락 페스티벌에 가려고 한다. 출발 할때 맥주 한박스(20병)를 들고 가서 50미터에 한 병씩 마시려고한다. 페스티벌을 가는 길에 맥주가 떨어질 수도 있느니 편의점에서 들러 맥주를 구매하여야한다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있으면 "happy"를, 아니면 "sad"를 출력한다.

 

 

bfs, dfs 문제를 안 푼지 좀 된것같아 감 잡을 겸 복습을 하고 있다.

너무 틀에 박힌 풀이를 해서 결국 힌트를 보고 풀었던 문제😢

역시 꾸준함이 가장 중요한 것을 느낀다.

 

풀이 )

처음엔 dp를 만들어서 count값이나 beer 값을 저장하려고 하였다.

그런데 풀면서도 이게 맞나..? 언제나 좋은 결과값을 저장할 필요가있나..? 생각을 계속 했다. 틀에 박힌 풀이의 문제점이 바로 이것...

 

그냥 distance를 찾아서 풀면 끝나는 어찌보면 간단한 문제였다.

• queue에 출발지(집)의 좌표를 넣어준다.
• 현재 좌표에서 목적지(페스티벌)까지 거리가 50m * 20병 = 1000 이내면 "happy"를 출력
• 목적지까지는 갈 수 없지만, 편의점까지 가는 거리가 50m * 20병 = 1000 이내이면 편의점에 간다.
• 목적지에 도착하지 않았는데 queue에 값이 없으면 페스티벌에 도착할 수 없으므로 "sad"를 출력한다.

from collections import deque

def distance(sx, sy, fx, fy):
    return (abs(sx-fx) + abs(sy-fy))

def bfs(home, festival):
    visited = set()
    queue = deque([home])
    
    while queue :
        x,y = queue.popleft()

        if distance(x, y, festival[0], festival[1]) <= 1000 :   # 페스티벌 도착
            return ("happy")
        
        for i in range(marketCount):
            ix, iy = market[i]
            if (ix, iy) not in visited :   # 방문안함
                if distance(x,y,ix,iy) <= 1000 :    # 갈 수 있는 편의점
                    visited.add((ix,iy))
                    queue.append([ix,iy])
    return ("sad")

for _ in range(int(input())) :  # 테스트케이스 t
    marketCount = int(input())
    home = list(map(int,input().split(' ')))
    market = list()
    for _ in range(marketCount):
        market.append(list(map(int,input().split(' '))))
    festival = list(map(int,input().split(' ')))
        
    print(bfs(home, festival))