9205. [Python] 맥주 마시면서 걸어가기

1. 문제

 

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

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

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• 그래프 탐색
• 너비 우선 탐색

 

3. 파이썬 코드

 

import sys
from collections import deque
# 많은 인풋 처리를 위해 sys 사용
input = sys.stdin.readline

T = int(input())
# 테스트 케이스 만큼 반복
for tc in range(T):
    store_cnt = int(input())
    # 편의점 위치 담을 리스트
    stores = []
    # 현재 시작 위치
    home = list(map(int,input().split()))
    # 편의점 위치 추가
    for _ in range(store_cnt):
        stores.append(list(map(int,input().split())))
    # 도착 지점 설정
    rock_festival = list(map(int,input().split()))
    # 갈 수 있는 지점 deque 를 이용한 queue 사용
    can_go = deque([])
    # 편의점 방문 체크
    visited = [0] * store_cnt
    # 집과 맥주 페스티벌의 거리가 1000 이하일 경우 바로 갈 수 있음
    if max(rock_festival[0],home[0]) - min(rock_festival[0],home[0]) + max(rock_festival[1],home[1]) - min(rock_festival[1],home[1]) <= 1000:
        print("happy")
    # 외의 경우
    else:
        # 현재 집에서 갈 수 있는 편의점 리스트 추가 후 방문여부 체크
        for index, store in enumerate(stores):
            if max(store[0],home[0]) - min(store[0],home[0]) + max(store[1],home[1]) - min(store[1],home[1]) <= 1000:
                can_go.append(store)
                visited[index] = 1
        # 갈 수 있는 편의점 리스트 순회
        while can_go:
            check = can_go.popleft()
            # 편의점에서 맥주 페스티벌까지 갈 수 있으면 정답 출력 후 반복문 종료
            if max(rock_festival[0],check[0]) - min(rock_festival[0],check[0]) + max(rock_festival[1],check[1]) - min(rock_festival[1],check[1]) <= 1000:
                print("happy")
                break
            # 편의점리스트 순회하며
            for index, store in enumerate(stores):
                # 현재 편의점에서 다음 편의점에 갈 수 있고 방문하지 않았으면 방문처리 후 갈 수 있는 리스트에 추가
                if max(store[0],check[0]) - min(store[0],check[0]) + max(store[1],check[1]) - min(store[1],check[1]) <= 1000:
                    if visited[index] == 0:
                        can_go.append(store)
                        visited[index] = 1
        # 반복문이 break로 탈출하지 못했을 경우 답 출력
        else:
            print("sad")

 

4. 문제를 풀고난 후 생각

 

• 초기 집에서 시작해 갈 수 있는 모든 편의점을 추가해 가며 방문여부를 체크한다.
• 이후 편의점에서 다시 방문하지 않았고 건너갈 수 있는 편의점들을 리스트에 더해 나가는 방식으로 리스트를 쌓아간다.
• 리스트의 값들을 출력하며 내가 도착할 지점에 도착할 수 있는지 체크하고 도착할 수 있으면 happy 를 도착하지 못하고 반복문이 끝나면 sad 를 출력한다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 너비 우선 탐색