[백준] 9205 - 맥주 마시면서 걸어가기 (파이썬, Python)

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

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

 

 

출발지(상근이의 집)에서 출발해서 목적지(페스티벌 장소)까지 갈 수 있는지 판단하는 것이 이 문제의 목표입니다.

단, 현재 장소에서 거리가 맨해튼 거리로 1000 이하인 다음 장소(편의점 또는 목적지)로만 이동 가능하다는 조건이 있습니다.

 

이 문제는 그래프 탐색 문제입니다.

탐색은 너비 우선(BFS)으로 진행해도 되고, 깊이 우선(DFS)으로 탐색해도 되는 거 같습니다.

저는 깊이 우선 탐색으로 진행했습니다.

 

접근 방식

1. 각 장소 별로 거리가 1000 이하에 있는 장소 정보를 저장합니다.

2. 출발지를 시작으로 주변 장소를 탐색합니다.

3. 2 단계의 결과 목적지까지 도달한다면 'happy'를 출력하고, 그렇지 않다면 'sad'를 출력합니다.

 

전체 코드

제출 언어: Python3

시간: 116ms

 

import sys

def solution():
    global n, spot, graph

    is_success = False
    
    visited = [ False ] * (n+2)
    visited[0] = True

    stack = [ 0 ]

    while stack:
        cur_spot = stack.pop()
        cx, cy = spot[cur_spot]

        if cur_spot == n+1:
            is_success = True
            break

        for next_spot in graph[cur_spot]:
            if not visited[next_spot]:
                visited[next_spot] = True
                stack.append(next_spot)

    return is_success


if __name__ == "__main__":
    t = int(sys.stdin.readline().strip())

    answer = []

    for _ in range(t):
        n = int(sys.stdin.readline().strip())

        spot = []

        graph = { i: [] for i in range(n+2) }

        for _ in range(n+2):
            cx, cy = map(int, sys.stdin.readline().strip().split())

            spot.append((cx, cy))

        for i in range(n+2):
            for j in range(i+1, n+2):
                x1, y1 = spot[i]
                x2, y2 = spot[j]

                if abs(x1-x2) + abs(y1-y2) <= 1000:
                    graph[i].append(j)
                    graph[j].append(i)

        is_success = solution()

        if is_success:
            answer.append("happy")
        else:
            answer.append("sad")

    for res in answer:
        print(res)