[Baekjoon 9205] 맥주 마시면서 걸어가기

문제

💛Ⅴ [Baekjoon 9205 - 맥주 마시면서 걸어가기 ]

문제 풀이 방법

처음 문제를 읽고 bfs문제라고 생각은 하였지만 바로 설계를 하는게 어려웠다. 다양한 그래프 알고리즘 문제들을 풀면서 dfs와 bfs문제들에 많이 익숙해졌다고 생각했지만 아닌 것 같다. 앞으로 꾸준히 더 많은 문제들을 풀어보아야 겠다고 생각이 들었다.

1. 집에서 출발하여 편의점들을 거쳐 페스티벌에 도착할 수 있는다면 True 를 없다면 False를 반환하는 bfs 함수를 작성한다.
   1. 큐에 시작 좌표를 넣는다.
   2. 큐가 빌 때까지 다음과정을 반복한다.
      1. 큐의 앞에서 좌표 하나(현재 위치)를 뽑는다.
      2. 도착지점까지의 거리가 1000(20*50)이하라면 True를 반환한다.
      3. 도착지점까지의 거리가 1000(20*50)이하가 아니라면 편의점 중 방문하지 않고 현재로부터 거리가 1000이하인 편의점을 큐에 넣고 b과정을 반복한다.
   3. 큐가 비었다면 도착지점까지 도달할 수 없는 것이므로 False를 반환한다.

풀이 코드

Python

import sys
from collections import deque
input = sys.stdin.readline

MAX_DISTANCE = 1000 # 20 * 50

def bfs(start, end, nodes):
    q = deque()
    q.append(start)

    while q:
        x,y = q.popleft()
        if abs(end[0] - x) + abs(end[1] - y) <= MAX_DISTANCE: # end 까지 도달할 수 있다면
            return True
        for node in nodes: # 편의점을 돌면서 방문할 수 있는 편의점을 큐에 추가한다.
            distance = abs(node[0] - x) + abs(node[1] - y)
            if not node[2] and distance <= MAX_DISTANCE:
                node[2] = True
                q.append([node[0],node[1]])
    return False

test_case = int(input())
for _ in range(test_case):
    market = int(input())
    home = list(map(int, input().split()))
    markets = [list(map(int, input().split())) + [False] for _ in range(market)]
    festival = list(map(int, input().split()))

    if bfs(home, festival, markets):
        print("happy")
    else:
        print("sad")