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

> 파이썬, 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

 

 

 

📖 문제 : 맥주 마시면서 걸어가기 (Python)

 

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

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

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

 

입력

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

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

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

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

 

출력

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

 

예제 입력 1 

2
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000

 

예제 출력 1

happy
sad

 

 

 

내 코드

from collections import deque


t = int(input())

for _ in range(t):
    market, house, festival = [], [], []
    market_cnt = int(input())

    x, y = map(int, input().split())
    house.append((x, y))

    for _ in range(market_cnt):
        x, y = map(int, input().split())
        market.append((x, y))

    x, y = map(int, input().split())
    festival.append((x, y))

    queue = deque([(house[0][0], house[0][1])])
    visited = [0] * market_cnt
    

    while queue:
        x, y = queue.popleft()

        if abs(x-festival[0][0]) + abs(y-festival[0][1]) <= 1000:
            print("happy")
            break
        else:
            for i in range(market_cnt):
                if abs(x-market[i][0]) + abs(y-market[i][1]) <= 1000 and visited[i] == 0:
                    visited[i] = 1
                    queue.append((market[i][0], market[i][1]))

    else:
        print("sad")

 

 

 

Point ! ⭐️ 

• 저는 이 문제를 맨처음에 봤을 때, '50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.' 라는 말로 50미터를 단위로 잡아, 50미터 갈 때마다 맥주를 하나씩 없애주는 방식으로 했는데, 이 방법은 시간 초과가 뜰 뿐더러
  
  ' 송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리) '
  이라는 조건을 사용하지 않더라구요 !
  
  

from collections import deque

t = int(input())
dx = [-50, 50]
dy = [-50, 50]

for _ in range(t):
    market, house, festival = [], [], []
    market_cnt = int(input())

    x, y = map(int, input().split())
    house.append((x, y))

    for _ in range(market_cnt):
        x, y = map(int, input().split())
        market.append((x, y))

    x, y = map(int, input().split())
    festival.append((x, y))

    bear = 20
    queue = deque([(house[0][0], house[0][1], bear)])
    dic = dict()  # 방문 했던 곳인지 구분하기 위해

    while queue:
        x, y, bear = queue.popleft()

        # 페스티벌에 도착
        if x == festival[0][0] and y == festival[0][1]:
            print("happy")
            break
        # 편의점에서 맥주 삼
        if (x, y) in market:
            bear = 20
        # 맥주가 없을 경우 더 이상 이동 불가
        if bear < 1:
            continue
        # x 값 -50m, +50m 이동
        for i in range(2):
            xx = x + dx[i]
            if -32768 <= xx < 32767 and -32768 <= y < 32767 and dic.get((xx, y, bear - 1), 0) == 0:
                queue.append((xx, y, bear - 1))
                dic[(xx, y, bear - 1)] = 1
        # y 값 -50m, +50m 이동
        for i in range(2):
            yy = y + dy[i]
            if -32768 <= x < 32767 and -32768 <= yy < 32767 and dic.get((x, yy, bear - 1), 0) == 0:
                queue.append((x, yy, bear - 1))
                dic[(x, yy, bear - 1)] = 1

    else:
        print("sad")

 

그래서 

' 송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리) '
이 조건을 가지고 더 간단히 코드를 짜면 되는 것이였더라구요 ?-? 

그리고 맥주 마시면서 걷는 기분은 무엇일까요, 한번도 안그래봤네요 :-)

 

 

 

백준

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

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