Coding Test/BaekJoon_Python

백준 9205 <맥주 마시면서 걸어가기> Python

JunOnJuly 2023. 10. 28. 22:40
728x90

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

 

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

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다.

www.acmicpc.net


전형적인 그래프 탐색 문제입니다. 다만 DFS 로 풀었다 시간초과가 발생해서 BFS 로 풀었습니다. 


from collections import deque


def solution(n, field):
    # 맵 정리
    start, field = field[0], field[1:]
    # BFS 로 풀거
    que = deque([start])
    # 방문 기록
    visited = [1 for _ in range(n+1)]

    while True:
        # 이동 가능 위치가 없으면
        if not que:
            return 'sad'
        # 현재 위치
        now = que.popleft()
        # 도착하면
        if not visited[-1]:
            return 'happy'
        for idx, store in enumerate(field):
            # 이동 가능 거리에 있고 방문한 적 없으면
            if (cal_distance(now, store) <= 1000) and \
                (visited[idx]):
                que.append(store)
                visited[idx] = 0


# 거리 계산
def cal_distance(idx1, idx2):
    return abs(idx1[0] - idx2[0]) + abs(idx1[1] - idx2[1])


t = int(input())

for _ in range(t):
    n = int(input())
    field = [list(map(int, input().split())) for _ in range(n+2)]
    print(solution(n, field))

 

728x90