[백준 9205번] 맥주 마시면서 걸어가기 파이썬 풀이

맥주 마시면서 걸어가기

1 초

128 MB

31995

13136

9639

39.690%

문제

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

 

'맥주를 마시면서 이동한다' 라는 문제 제목때문에, dx,dy를 이용하여 모든 좌표를 하나씩 방문하며 bfs를 수행하다 50m씩 이동할때마다 맥주의 개수를 카운팅 해주어야하나? 라는 생각이 제일 먼저 들었지만 생각해보니 모든 좌표를 하나씩 방문하는것은 말도 안되는 생각이라는 것을 깨달았고, 그 다음으로 들은 생각은 이동하는 좌표를 50m씩 이동하며 큐에 좌표와 함께 현재 시점에서의 맥주의 개수를 삽입해서 bfs 수행시 맥주의 잔여량을 보고 진행하는 방식을 떠올렸으나 좌표값이 50의 배수로 딱 나누어 떨어지지 않을것이고, 그걸 해결할 방법을 찾는다고 하여도 구현이 너무 복잡할것같았고 너무 복잡하게 생각하는게 아닌가 고민하게 되었다.

 

이 문제의 해결방법은 현재위치,편의점의 좌표들, 목적지를 하나의 정점으로 보는것이다.

즉 좌표값들을 각 정점의 요소로 생각하고 결국 방문 하는 장소들은 현재 위치에서 목적지를 향해 이동하거나, 편의점에 방문하였다가 목적지로 이동하거나 둘 중 하나이므로, 정점으로 규정한 현재위치, 편의점, 목적지에 대해서 bfs를 수행하면 된다는것이다.

또한 맥주가 20병이 있다는 소리는, 한번에 최대 1000m를 이동 가능하다는 의미이고(20병 x 50m) 한 정점에서 다른 정점까지의 거리가(두 좌표의 차의 합) 1000이하라면, 해당 좌표를 방문 가능하다는 의미가 될것이다.

 

따라서 내 현재 위치에서 목적지로 바로 방문이 가능한지 확인하고(좌표의 차가 1000이하인지 확인하고), 만약 그렇다면 "happy"를 출력하고, 그렇지 않다면 알고 있는 편의점의 좌표들을 대상으로 마찬가지로 방문이 가능한지 확인하고 bfs를 수행하면서 이동한 좌표들에 대해 목적지로 방문이 가능한지 확인하면된다.

 

앞서 말한 설명들을 코드로 바꾸면 아래와 같다.

from collections import deque
t = int(input())


def bfs(s, e):
    queue = deque()
    queue.append([s, e])

    # 편의점 개수만큼 방문정보를 확인해야하므로 배열 생성
    visited = [False for _ in range(n)]

    while queue:
        x, y = queue.popleft()
        # 현재 위치에서, 목적지에 도달하는것이 가능한지(이동거리 1000으로 이동할수 있는지) 확인
        if (abs(goal_x-x) + abs(goal_y-y)) <= 1000:
            return "happy"  # happy 리턴

        # 목적지에 아직 도달하지 못하였다면, bfs수행
        # 편의점 좌표들 하나씩 방문
        for i in range(n):
            # i번째 편의점 에 아직 방문하지 않은 경우에만 방문
            if not visited[i]:
                # 해당 편의점에 방문이 가능한지 확인(두 좌표의 차의 합이 1000이하인지 확인)
                if (abs(conveni[i][0]-x) + abs(conveni[i][1]-y)) <= 1000:
                    visited[i] = True  # 해당 편의점 방문처리
                    # 편의점의 좌표를 큐에 삽입하여, 상근이를 이동시킴
                    queue.append([conveni[i][0], conveni[i][1]])

    # 탐색 실패시 sad 리턴
    return "sad"


for _ in range(t):
    n = int(input())
    # 현재 상근이의 위치
    s, e = map(int, input().split())
    # 편의점 좌표들
    conveni = [list(map(int, input().split())) for _ in range(n)]
    # 최종 목적지
    goal_x, goal_y = map(int, input().split())
    print(bfs(s, e))

 

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

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