[python] 백준 9205번 : 맥주 마시면서 걸어가기 (BFS, DFS)

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

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

 

맥주는 총 20병이 있고 50미터에 1병씩 맥주를 까서 마신다. 즉, 시작 지점(상근이네 집)과 도착지점(맥주 페스티벌)의 거리가 1000미터 이내이면 행복하게 한잔씩 까면서 무사히 도착할 수 있다.  

 

- 상근이네 집과 페스티벌 장소까지의 거리가 1000m 이내이면 : True

- 1000m이내가 아닐 경우 편의점에 들리면 맥주가 다시 20병까지 채워진다. 즉 상근이네 집부터 편의점까지 거리가 1000m 이내이고 편의점부터 페스티벌 장소까지의 거리가 1000m이내 이면 : True

- True를 리턴하는 경우 페스티벌 장소까지 무사히 도착할 수 있기에 'happy'를 출력한다. 

- 그 외의 경우는 False : 더이상 이동할 수 없으므로 'sad'가 출력된다.

 

 

[BFS]

from collections import deque

def distance(xa, yb, xc, yd):
    return abs(xa-xc) + abs(yb-yd)

def bfs(x, y):
    global end_x, end_y
    deq = deque([(x, y)])
    visited = set()

    while deq:
        x, y = deq.popleft()
        if distance(x, y, end_x, end_y) <= 1000:
            return True
        for i in range(s):
            store_x, store_y = store[i]
            if (store_x, store_y) not in visited:
                if distance(x, y, store_x, store_y) <= 1000:
                    visited.add((store_x, store_y))
                    deq.append((store_x, store_y))
    return False


for _ in range(int(input())):
    s = int(input())
    start_x, start_y = map(int, input().split())
    store = [tuple(map(int, input().split())) for _ in range(s)]
    end_x, end_y = map(int, input().split())
    check = bfs(start_x, start_y)
    print('happy' if check else 'sad')

[DFS]

def distance(xa, yb, xc, yd):
    return abs(xa-xc) + abs(yb-yd)

def dfs(x, y, status):
    global end_x, end_y, visited
    # 상근이네에서 페스티벌까지 1000m 이내인 경우
    if distance(x, y, end_x, end_y) <= 1000:
        return True
    for i in range(s):
        store_x, store_y = store[i]
        if distance(x, y, store_x, store_y) <= 1000:
            if not visited[i]:
                visited[i] = True
                status = dfs(store_x, store_y, status)
    return status


for _ in range(int(input())):
    s = int(input())
    start_x, start_y = map(int, input().split())
    store = [tuple(map(int, input().split())) for _ in range(s)]
    end_x, end_y = map(int, input().split())
    visited = [False for _ in range(s)]
    check = dfs(start_x, start_y, False)
    print('happy' if check else 'sad')