[백준] 9205 맥주 마시면서 걸어가기

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

특정 지점(출발점과 이동이 가능한 편의점)에서 맥주 20병을 가지고 최대로 이동할 수 있는 범위 내에 도착지나 편의점이 있는지 여부를 탐색하였습니다.

2) 알고리즘

• 너비 우선 탐색

3) 풀이 코드

사용 언어 - Python

import sys
from collections import deque
sys.stdin = open('input.txt')

T = int(sys.stdin.readline())       # 테스트케이스 개수

for _ in range(T):
    N = int(sys.stdin.readline())   # 편의점의 개수

    start = list(map(int, sys.stdin.readline().split()))                                # 집의 좌표
    coordinates = [list(map(int, sys.stdin.readline().split())) for _ in range(N+1)]    # 편의점, 목적지 좌표

    visited = [0] * (N+1)               # 편의점과 목적지를 방문했는지 여부
    can_move = set()                    # 맥주 마시며 갈수 있는 장소들 집합

    q = deque([start])
    while q:
        node = q.pop()
        can_move.add(tuple(node))       # 현재 위치를 갈 수 있는 집합에 추가 

        for i in range(N+1):
            if not visited[i] and abs(coordinates[i][0] - node[0]) + abs(coordinates[i][1] - node[1]) <= 1000:      # 아직 확인하지 않은 장소이고, 맥주 20병으로 갈 수 있는 거리인 경우
                visited[i] = 1                      # 확인 체크
                q.append(coordinates[i])            # 다음 확인을 위해 추가

    if tuple(coordinates[-1]) in can_move:      # 목적지에 갈 수 있으면 happy 출력
        print('happy')
    else:
        print('sad')

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

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

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다