[알고리즘][Python] 백준 9205 맥주 마시면서 걸어가기 문제 풀이

문제 출처 : www.acmicpc.net/problem/9205

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

---

문제 해석 : 50미터 마다 목이 마르지 않게 맥주를 마신다. 이때 목적지까지 목이 마르지 않게 도착할 수 있는지 주어진 편의점과 시작, 도착점의 거리를 이용해서 계산하는 문제이다.

 

문제 풀이 :  BFS와 플루이드 - 와셜 알고리즘을 이용해서 풀이 할 수 있다. 입력을 통해서 이동 가능한 곳을 1로 표시하고 아닌 곳은 INF로 표시한 다음 모든 가능성에 대해서 검사하고 possible[0]N+1]이 INF인지 아닌지 검사하면 된다.

---

풀이 코드

T = int(input())

for test_case in range(T):
    N = int(input())
    arr = []
    arr.append(list(map(int, input().split())))
    for _ in range(N):
        arr.append(list(map(int, input().split())))
    arr.append(list(map(int, input().split())))

    possible = [[int(1e9)] * (N+2) for _ in range(N+2)]

    for i in range(N+2):
        for j in range(N+2):
            if i != j:

                diff = abs(arr[i][0] - arr[j][0]) + abs(arr[i][1] - arr[j][1])
                if diff <= 1000:
                    possible[i][j] = 1

    for k in range(N+2):
        for a in range(N+2):
            for b in range(N+2):
                possible[a][b] = min(possible[a][b], possible[a][k] + possible[k][b])
    if possible[0][N+1] == int(1e9):
        print("sad")
    else:
        print("happy")

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.