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

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

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

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:15:56

 

---

 

문제 설명

 

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 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

 

 

---

 

풀이

 

여러 가지 가정 (이를테면, 맥주를 마시고 20걸음이 남은 상태에서 편의점에 들리면 1000 + 20걸음을 더 걸을 수 있는 거 아닌가...?) 이 있었지만, 그런 거 없었다. (편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다. 이 문장이 돌이켜 생각해 보면 저런 가정을 막아주는 것 같다)

 

50걸음당 맥주 한 병. 총 20개의 맥주를 들 수 있으므로 한 지점부터 다음 지점까지 갈 수 있는 최대 거리는 1000이 된다. 즉,

 

• 거리가 1000 이하인 두 지점을 모두 이은 그래프를 그려 주고
• 그래프의 시작 지점에서 탐색을 시작해 끝 지점까지 갈 수 있는지 여부를 판단하면 된다.

 

여기서 탐색 알고리즘은 다익스트라도 좋고, DFS나 BFS를 사용해도 된다. 어쨌든 여부만을 판단하는 거니까.

 

• init : 초기화함수. 정수 N과 N+2개줄의 좌표 리스트를 입력받아, 위의 설명을 토대로 한 graph를 작성하여 반환한다.
• dijkstra : 다익스트라 알고리즘. 여기서는 heapq를 사용했다. 핵심은 시작 지점에서 graph의 인접 노드들을 방문하며 끝 지점까지 도달할 수 있는지를 판단한다. 그 여부를 boolean값으로 반환한다.
• solve : 메인함수. T개의 test케이스 동안 init과 dijkstra 함수를 호출하여 그 여부를 happy 혹은 sad로 출력한다.

 

풀이 코드

from heapq import *
import sys

input = sys.stdin.readline
MAX = float('inf')

def init() :
  N = int(input())
  coord_list = [list(map(int, input().split())) for _ in range(N+2)]

  graph_mat = { key : [] for key in range(N+2)}

  for i in range(N+1) :
    ix, iy = coord_list[i]
    for j in range(i+1, N+2) :
      jx, jy = coord_list[j]
      dist = abs(ix - jx) + abs(iy - jy)
      if dist <= 1000 :
        graph_mat[i].append(j)
        graph_mat[j].append(i)

  return N, graph_mat

def dijkstra(N, graph_mat) :
  visited = [MAX]*(N+2)
  visited[0] = 0
  q = [(0, 0)]

  while q :
    dist, node = heappop(q)
    if node == N+1 :
      return True

    next_dist = dist + 1
    for next_node in graph_mat[node] :
      if visited[next_node] > next_dist :
        visited[next_node] = next_dist 
        heappush(q, (next_dist, next_node))

  return False

def solve() :
  T = int(input())
  for i in range(T) :
    N, graph_mat = init()
    is_enable = dijkstra(N, graph_mat)
    print("happy" if is_enable else "sad")

solve()

 

풀이 완료~