[BOJ] 백준 9205번 - 맥주 마시면서 걸어가기(with Java)

알고리즘

아이디어를 떠올릴 수 있다면, Floyd-Warshall 알고리즘을 이용해서 간단하게 BFS로 풀 수 있는 문제이다.

 

설계를 잘했다면 문제를 푸는 방법은 매우 간단하다.

우선, 각각의 위치를 정의해줘야만 하는데 좌표가 음수가 될 수도 있으므로 배열을 이용한 풀이는 어렵다.

따라서 현재 위치 x, y 좌표와 해당 위치의 방문 여부 정보 및 시작점과의 거리 정보를 담고 있는 클래스를 만들어준다.

또한, 모든 편의점과 목적지는 시작점과의 거리 정보를 무한대로 설정해주고 각각의 객체들을 리스트에 넣어준다.

 

이제부터 각각의 정점들에 대해서 BFS를 수행하면 되지만, 여기서 고려해줘야할 사항이 하나 있다.

문제에서 주어진 '맥주 한 박스에는 맥주가 20개 들어있다', '50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다'라는 조건에 따라서 현재 위치에서 다음 편의점 또는 목적지까지의 거리가 1000미터 이하여만 한다는 것이다.

 

따라서 현재 위치에서 다음 편의점 또는 목적지까지의 거리가 1000 이하인 정점에 대해서만 BFS를 수행해야 한다.

또한, 만약에 거리가 1000 이하라면 시작점과 다음 정점까지의 거리를 현재 위치에서 다음 정점까지의 거리로 바꿔준다.

다음에 방문하려는 정점은 거리가 1000 이하이므로, 방문 예정으로 표시해주고 BFS를 수행하기 위해서 큐에 넣어준다.

BFS가 종료되면 리스트의 마지막에 있는 객체(목적지)를 꺼내서 해당 객체의 거리 정보를 출력용 리스트에 넣어준다.

 

각각의 테스트케이스에 대해서 위의 알고리즘을 반복해주면 된다.

마지막으로 출력용 리스트에 들어있는 각각의 거리 정보를 확인해서 무한대면 'sad', 그렇지 않으면 'happy'를 출력한다.

소스코드

문제링크

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