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

📍문제 링크

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

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

 

📍알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

 

📍문제 풀이

문제를 이해하기 조금 힘들었따..

 

출발점, 도착점, 휴식지점 좌표가 주어진다

한 번에 갈 수 있는 거리는 1000 (맨해튼 거리 기준)

 

출발점에서 도착점까지 휴식지점을 거치든 안거치든 갈 수 있는지 묻는 문제이다

 

BFS를 쓰든 DFS를 쓰든 해결할 수 있지만, 경로를 구하는 문제가 아니므로 BFS를 사용한다

 

📍의사 코드

1. 출발지점에서 도착지점까지 거리가 충족되면 바로 Pass- 아니라면 중간 휴식지점을 이용해서 도착지점까지 가야함

 

2. 출발지점에서 모든 휴식지점 리스트를 순회하며 아직 미방문인데 거리 기준이 충족되면 큐에 넣고 방문 표시한다- 출발 다음에 방문할 지점 확인

 

3. 큐에서 하나씩 빼면서 도착지점과 거리 비교하여 기준 되면 Pass- 아니라면 큐에서 뺀 중간 휴식지점을 출발지점으로 삼아서 미방문한 휴식지점중 거리 기준 충족되는 좌표를 다시 큐에 넣음- 이 과정을 반복하면서 경로를 넓혀가다가 도착지점과 거리 기준 충족되면 Pass

 

4. 가능한 중간 휴식 지점을 모두 돌았는데 도착지점까지 너무 멀면 (큐에 원소 없으면) Fail 처리 후 종료

 

📍코드

from collections import deque


def is_walkable(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2) <= 1000


def bfs():
    d = deque([start])
    while d:
        x, y = d.popleft()
        if is_walkable(x, y, final[0], final[1]):
            return "happy"
        for i in range(n):
            if not visited[i]:
                stop_x, stop_y = stops[i]
                if is_walkable(x, y, stop_x, stop_y):
                    d.append([stop_x, stop_y])
                    visited[i] = True
    return "sad"


t_num = int(input())
for i in range(t_num):
    n = int(input())
    start = [int(x) for x in input().split()]
    stops = []
    for j in range(n):
        x, y = map(int, input().split())
        stops.append([x, y])
    final = [int(x) for x in input().split()]
    visited = [False for i in range(n + 1)]  # 출발 지점 빼고 아예 리스트 생성
    print(bfs())