[코딩테스트][백준] 🔥 백준 9205번 "맥주 마시면서 걸어가기" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 30분

from collections import deque
def bfs(pos):
    visited=[False]*(len(pos))
    visited[0]=True
    q=deque()
    q.append(0)
    while q:
        now=q.popleft()
        for i in range(1,n+2):
            dist=abs(pos[i][0]-pos[now][0])+abs(pos[i][1]-pos[now][1])
            if dist<=1000 and not visited[i]:
                if i==n+1:
                    return True
                visited[i]=True
                q.append(i)
    return False

for _ in range(int(input())):
    n=int(input())
    pos=[]
    for _ in range(n+2):
        pos.append(tuple(map(int,input().split())))
    if bfs(pos):
        print("happy")
    else:
        print("sad")

맥주 마시며 축제 가기! 🍻🎉

맥주 마시면서 축제로 가는 문제이다. 처음에는 DFS문제로 접근하였으나 시간초과가 나길래 BFS로 접근하였다. 접근 방식은 비슷한데 아마 시간부분이 디테일한가보다...

처음 시작할 때 집을 시작으로 아직 방문하지 않았고 현지점으로 부터 거리가 1000보다 작은 곳을 방문한다. 50미터씩 20개가 완전히 충전한 상태이기 때문에 1000 이하로 잡으면 되기 때문이다. 그러던 중, 축제에 방문하는 순간 return을 True로 하여 Happy를 출력하면 되고 아니면 sad를 출력하면 된다. 단순한 그래프 문제이다.

이렇게 Python으로 백준의 "맥주 마시면서 걸어가기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊