[🥈1 / 백준 9205 / 파이썬] 맥주 마시면서 걸어가기

 

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

 

문제

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

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

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

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다. 

 

예제 입력 2 2 0 0 1000 0 1000 1000 2000 1000 2 0 0 1000 0 2000 1000 2000 2000

예제 출력 happy sad

 

풀이

 

시작점부터 도착점까지 경유지를 거치면서 최대 1000의 거리를 넘지 않으며 도착할 수 있는지 판별하는 문제이다.

플로이드-와샬 태그가 붙어 있지만, 알고리즘 특성상 O(N³)이기 때문에 상당히 느려 BFS로 해결하는 것을 추천한다.

 

그래도 플로이드 와샬로 해결하는 방법을 짚고 넘어가도록 하자.

우선 인접 행렬이 없기 때문에 직접 만들어주어야 한다.

정점들의 거리를 비교하여 맨해튼 거리가 1000을 넘지 않는다면, 인접 행렬에 1을 기록하여 준다.

비교가 끝나면 플로이드-와샬을 진행한다.

 

import sys
input = sys.stdin.readline

def get_dist(pos1,pos2):
    return abs(pos2[0]-pos1[0]) + abs(pos2[1]-pos1[1])

def solve():
    for _ in range(int(input())):
        n = int(input())+2
        pos = [tuple(map(int,input().split())) for i in range(n)]
        board = [[float('inf')]*n for i in range(n)]
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                if get_dist(pos[i],pos[j]) <= 1000:
                    board[i][j] = 1

        for k in range(n):
            for i in range(n):
                for j in range(n):
                    board[i][j] = min(board[i][j], board[i][k]+board[k][j])
        print("happy" if board[0][n-1] < float('inf') else "sad")
solve()

 

문제가 풀리기는 하나, 모든 정점에서 다른 모든 정점으로 가는 경로까지 계산해야 하므로 상당히 느리다.

따라서 BFS로 시작점부터 도착점까지의 최단 거리만 찾아주도록 하자.

 

BFS는 인접 리스트 방식으로 해결했다.

마찬가지로 정점 간의 거리가 1000 이하일 경우에만 간선을 추가해준 뒤, BFS를 진행하면 된다.

 

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

def get_dist(pos1,pos2):
    return abs(pos2[0]-pos1[0]) + abs(pos2[1]-pos1[1])

for _ in range(int(input())):
    n = int(input())+2
    board = [[float('inf')]*n for i in range(n)]
    link = [[] for _ in range(n)]
    pos = [tuple(map(int,input().split())) for i in range(n)]
    # 인접 리스트 생성
    for i in range(n-1):
        for j in range(i,n):
            if i==j: 
                continue
            d = get_dist(pos[i],pos[j])
            if d > 1000:
                continue
            link[i].append(j)
            link[j].append(i)
    
    visit = [False]*n
    q = deque([0])
    while q:
        curNode = q.popleft()
        if visit[curNode]:
            continue
        visit[curNode] = True
        # 락페 도착
        if curNode == n-1:
            print("happy")
            break
        
        for toNode in link[curNode]:
            if not visit[toNode]:
                q.append(toNode)
    else:
        print("sad")