[백준-9205] 맥주 마시면서 걸어가기 - Python

 

 

문제 소개

 

문제

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

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

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

 

 

 

 

사용한 알고리즘

 

 

DFS,BFS,플로이드 와샬 알고리즘을 이용한 문제  풀이가 가능하다고 한다

나는 DFS를 사용하여 풀었다

 

 

 

 

Code 

 

#############################################################################
#
#############################################################################

import sys
import collections



sys.stdin = open("input.txt", "r")

input=sys.stdin.readline



def distance(x,y):
    return abs(x[0] - y[0]) + abs(x[1] - y[1])


check = 0
def DFS(x,y,cur_dis,check_arr):
    global check
    if x==Ex and y==Ey :
        check = 1
        return print("happy")
    for p in graph:
        if check_arr[p+1]==0 and distance([x,y], graph[p]) <= 1000:
            check_arr[p + 1] = 1
            DFS(graph[p][0],graph[p][1],visited_and_dist[p],check_arr)


T = int(input())

for _ in range(T):

    PNum = int(input())
    Ox,Oy = list(map(int,input().split()))

    graph = collections.defaultdict()

    check_arr = [0 for _ in range(PNum + 2)]
    check_arr[0] = 1

    for k in range(PNum):
        graph[k]=list(map(int,input().split()))
    Ex,Ey = list(map(int,input().split()))
    graph[PNum]=[Ex,Ey]

    visited_and_dist = []
    for p in graph:
        visited_and_dist.append(abs(graph[p][0]-graph[PNum][0])+abs(graph[p][1]-graph[PNum][1]))


    check = 0
    DFS(Ox, Oy, float('inf'),check_arr)
    if check == 0 :
        print('sad')

 

 

 

마무리

 

사용한 반례

4
4
2000 0
1000 0
0 0
0 1000
0 2000
1000 2000
0
1000 1000
1000 1001
1
0 0
1000 0
0 2000
2
0 0
10000 0
0 1000
0 2000

 

정답 :

happy

happy

sad

happy

 

※ end