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

Jimeaning·2023년 7월 9일

BFS 그래프

코딩테스트

목록 보기

109/143

Python3

문제

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

키워드

그래프 탐색
너비 우선 탐색

문제 풀이

문제 요구사항

출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. (맥주 한 박스당 20개)
50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어지고, 상근이네 집에서 출발해 펜타포트 락 페스티벌까지 도착해야 한다. 중간에 맥주를 사러 편의점을 들릴 수 있다. 이때 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이이다.

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

변수 및 함수 설명

t: 테스트 케이스의 개수 (t ≤ 50)
n: 편의점의 개수 (0 ≤ n ≤ 100)
home: 상근이네 집 좌표
adjList: 편의점 좌표
fest: 펜타포트 락 페스티벌 좌표
(x, y 좌표 두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

visited: 방문 처리 리스트
queue: bfs에 사용하는 큐
curX, curY: 현재 좌표
nx, ny: 다음 이동할 좌표

bfs(): 너비 우선 탐색 함수

풀이

(입력 및 선언)

테스트 케이스 개수를 입력받고, 해당 수만큼 반복한다
편의점 개수를 입력받고, 상근이네 집 좌표와 편의점 좌표, 락 페스티벌 좌표를 차례로 입력받아 리스트에 저장한다.
방문 처리 리스트를 선언하고 초기화한다.

(bfs 함수)

큐를 선언하고, 집 좌표를 큐에 넣는다.
큐에 원소가 없을 때까지 반복한다.
큐의 첫 번째 좌표를 꺼내 curX, curY 변수에 저장한다.
만약 현재 x좌표와 페스티벌 x좌표의 차이와 현재 y좌표, 페스티벌 y좌표의 차이를 더했을 때 맥주가 부족하지 않다면 happy를 리턴한다.
= 즉, 맥주는 한 병 당 50m씩 갈 수 있고 한 박스 당 20병이 들었으므로 총 1000미터를 갈 수 있는 것이다.
편의점의 개수만큼 반복문을 수행한다.
만약 방문하지 않은 곳이라면, 해당 편의점 좌표를 nx, ny 변수에 저장한다.
이때 현재 x좌표와 편의점 x좌표의 차이와 현재 y좌표, 편의점 y좌표의 차이를 더했을 때 1000보다 작거나 같으면
큐에 편의점 좌표를 넣고, 방문 처리를 한다.
큐를 다 돌고도 거리가 남아 있다면 더이상 가지 못하는 것이므로 sad를 리턴한다.

최종 코드

from collections import deque

t = int(input())

def bfs():
    queue = deque([])
    queue.append([home[0], home[1]])
    while queue:
        curX, curY = queue.popleft()
        if abs(curX - fest[0]) + abs(curY - fest[1]) <= 1000:
            return 'happy'
            
        for element in range(n):
            if not visited[element]:
                nx, ny = adjList[element]
                if abs(curX - nx) + abs(curY - ny) <= 1000:
                    queue.append([nx, ny])
                    visited[element] = 1
    return 'sad'

for _ in range(t):
    n = int(input())
    adjList = []
    
    home = [int(x) for x in input().split()]

    for _ in range(n):
        x, y = map(int, input().split())
        adjList.append([x, y])

    visited = [0 for _ in range(n+1)]
    fest = [int(x) for x in input().split()]
    
    print(bfs())