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

 

www.acmicpc.net/problem/9205

---

그래프 탐색문제입니다.

 

상근이네 집 -> 페스티벌 장소까지 중간에 편의점을 경유하든 안하든 도달할 수 있는지 묻습니다.

 

한 장소에서 맥주를 20개까지 충전가능하기에 정점과 정점사이의 거리가 1000m 이하일 때만 이동 가능합니다.

 

바꿔말하면,

1. 플로이드 알고리즘을 통해 정점과 정점 사이의 거리를 모두 구하기

2. BFS를 돌면서 상근이네 -> 페스티벌 장소까지 이동가능 여부 판단

위 두 가지 과정을 거치면 됩니다.

 

다음 노드를 큐에 넣을 수 있는지 판별여부는 현재 노드와 다음 노드의 거리가 1000m 이하인지 체크하면됩니다.

---

코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ9205.cc