[백준] 9205: 맥주 마시면서 걸어가기 python 구현 / DFS

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

풀이

처음엔 왜 꼭 그래프 문제로 풀어야 하는지 이해가 가지 않았다. 그러나 편의점이 순서대로 주어지지 않을 경우 for문으로 풀지 못함을 깨닳았다. 예시로 아래 처럼 문제가 들어온다면 정답은 "happy"지만 for문으로 풀게되면 "sad"를 출력한다.

1
2
0 0
1000 0
2000 1000
1000 1000

CODE

import sys
t = int(input())

def dfs(x, y):
    global feel

    if abs(x - fx) + abs(y - fy) <= (20*50): # 현재 위치에서 도착지(festival)까지 갈 수 있으면
        vst[-1] = 1 # 마지막 도착지 방문처리
        return 

    for idx in range(0, n+1):  #festival 장소 제외, 편의점을 돌면서 위 if문에 걸릴때 까지?
        if vst[idx]: continue

        nx, ny = coor[idx][0], coor[idx][1]
        dist = abs(x - nx) + abs(y - ny) # 현재 장소와 다음장소간 거리 측정
        
        if dist <= (20 * 50):
            vst[idx] = 1
            dfs(nx, ny)   # 방문처리 하고 현재 장소 변경 (x-> nx)

f_list = []
for _ in range(t):
    n = int(input())
    coor = [] 
    for _ in range(n+2):
        coor.append(list(map(int, sys.stdin.readline().split())))
    
    hx, hy = coor[0][0], coor[0][1] # home
    fx, fy = coor[-1][0], coor[-1][1] # festival 
    vst = [0] * (n+2)

    feel = "happy"
    vst[0] = 1 # 출발지는 방문
    dfs(hx, hy) # home 에서 부터 출발
    if not vst[-1]: # 마지막 도착지(festival)에 방문이 안됐으면
        feel = "sad"

    f_list.append(feel)

for i in f_list:
    print(i)