백준 문제 풀이 Python
[백준/Python] 9205번: 맥주 마시면서 걸어가기
골슼
2022. 11. 27. 16:34
문제 제목이 너무 낭만 넘치네요.
오늘도 최근에 풀던 것과 같이 BFS를 이용한 간단한 문제풀이가 되겠습니다!
-문제
https://www.acmicpc.net/problem/9205
9205번: 맥주 마시면서 걸어가기
송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다.
www.acmicpc.net
-문제 이해
조건 및 장치들
- 맥주는 총 20병을 가지고 있을 수 있으며 맥주 한 병당 50m를 갈 수 있다.
즉, 편의점을 들르지 않고 최대 1000미터를 갈 수 있다.
- 편의점을 들르면 다시 맥주를 리필하기에, 편의점부터 1000미터를 더 갈 수 있다.
- 거리는 맨해튼 거리로 측정한다.
-풀이
방법은 꽤 단순해요.
시작지점부터 상근이가 거쳐가는 모든 지점에서 목표장소까지의 거리가 1000미터를 넘지 않는 곳이 한 곳이라도 있으면
'happy'를 출력해주면 돼요.
상근이가 거쳐갈 지점들은 곧 편의점들이 되는 것이고, 입력받는 편의점을 위치를 cvs라는 리스트에 저장해요.
그리고 너비우선탐색을 이용해서 각 편의점에서 이동할 수 있는 다른 편의점을 조사하고 각각의 편의점에서 축제 장소로 갈 수 있는지도 조사해주면 완성이에요!
-소스코드
import sys
input = sys.stdin.readline
from collections import deque
def distance(x, x_t, y, y_t):
return abs(x - x_t) + abs(y - y_t)
def bfs(x, y):
visited = [0] * c_nums
coor = deque([(x,y)])
while coor:
x, y = deque.popleft(coor)
if distance(x, goal[0], y, goal[1]) <= 1000:
return 'happy'
for i in range(c_nums):
if not visited[i] and distance(x, cvs[i][0], y, cvs[i][1]) <= 1000:
visited[i] = 1
coor.append((cvs[i][0], cvs[i][1]))
return 'sad'
t = int(input())
for _ in range(t):
c_nums = int(input())
st = list(map(int, input().split()))
cvs = [list(map(int, input().split())) for _ in range(c_nums)]
goal = list(map(int, input().split()))
print(bfs(st[0], st[1]))