[백준] 9205번 : 맥주 마시면서 걸어가기

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

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

해당문제는 BFS탐색 문제로 현재 위치에서 갈 수 있는 최단경로를 구해야하는 문제이다. 해당 위치로 부터 갈 수 있는 거리를 구해서 탐색하면 된다. 맥주 1병을 마시면 50미터를 갈 수 있으니 상근이는 20병을 담을수 있는 상자를 들고 다니니 20*50 = 1000 의 거리까지 갈 수 있다. 따라서 현재 위치에서 1000미터 까지의 거리가 탐색 조건이다.

 

해당 문제를 처음에는 깊이우선 탐색으로 진행 하였으나 방문 체크 여부를 확인하는 로직을 잘 못 설계하여 시간복잡도 문제가 발생하였다.

최단 거리를 구하는 문제는 BFS 탐색으로 접근해야 좀 더 쉽게 풀 수 있다.

 

import sys
from collections import deque
input = sys.stdin.readline
t = int(input()) # 테스트 케이스 개수     

            
for _ in range(t):
    n = int(input()) # 편의점 개수
    house = list(map(int, input().split())) # house[0] x좌표 house[1] y좌표
    destnation = []
    festival = [] # 페스티벌 좌표 festival[0] x좌표, festival[1] y좌표 festival[2]는 도착idx
    

    destnation.append([house[0], house[1], 0])
    for i in range(n+1):
        dest = list(map(int, input().split()))
        dest.append(i+1)
        if i == n:
            festival = dest
        destnation.append(dest) # 모든 경로를 지정한다.
    finishedFlag = False
    

    visited = [False for _ in range(n+2)] # 도착 여부를 체크하는 리스트
    
    queue = deque()
    queue.append([house[0], house[1], 0])
    visited[0] = True
    while queue:
        newx, newy, index = queue.popleft()
        
        if index == festival[2]:
            finishedFlag = True
            break
        
        for dest in destnation: # 여기서 
            x,y, idx = dest
            if 1000 >= abs(x-newx) + abs(y-newy) and not visited[idx]: # 맥주 20개 x 50미터 갈 수있음. 거리가 1000 이상인 목적지와 방문하지 않는 목적지만 탐색한다.
                queue.append([x,y,idx])
                visited[idx] = True
    
    if finishedFlag :
        print("happy")
    else:
        print("sad")