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

문제 

상근이는 20병의 맥주를 가지고 있고 50미터에 한 병씩 마시며 목적지에 도착해야한다. 출발지와 목적지 사이에 맥주를 파는 편의점이 주어질 때 상근이가 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/9205)

풀이

처음에 문제를 봤을 때는 주어지는 좌표도 너무 넓어서 50으로 나눠서 관리를 해줄지.. 등의 생각이 많이 드는 문제였는데 하나의 힌트로 쉽게 해결할 수 있는 문제였습니다. 편의점을 통해서 그래프를 그리는 것입니다. 처음에 20병으로 시작하게되고 어느 편의점을 들리던지 먹은만큼 맥주를 살 수 있기 때문에 편의점에 들리게 되면 20병으로 다시 채워집니다. 남은 병수와 관계없이 20병안으로 편의점을 거쳐갈 수 있다면 계속해서 이동이 가능합니다. 20병안으로 라는 뜻은 X좌표 사이의 거리/50 + Y좌표 사이의 거리/50 이 20보다 작거나 같아야합니다. 이렇게 되면 처음 출발좌표, 편의점 좌표, 페스티벌 도착지 좌표를 하나의 그래프로 그려서 20병 안으로 이동할 수 있는 거리라면 연결해주어서 인접리스트를 만들 수 있습니다. 인접리스트를 만들고나면 더 간단합니다. BFS를 통해서 첫 출발좌표를 큐에 넣어주고 마지막 좌표에 도착할 수 있는지 확인하면 됩니다. 연결되어 있다는 것은 20병으로 이동할 수 있다는 것이고 편의점을 거치면 다시 20병이 되므로 또 다시 이동을 할 수 있고 최종 목적지에 연결되어있다는 것이 무사히 도착할 수 있음을 뜻합니다. 나누기를 할 때에 int형이 아닌 float를 써줘야 한다는 점과 테스트케이스가 여러개 주어지므로 초기화를 잘 해결해주면 됩니다!(저는 초기화를 잘못해주어서 한번 틀렸습니다를 받았습니다.)

코드

https://github.com/kswim/Algorithm/blob/master/BFS/9205.cpp