[백준 / Java] 9205번: 맥주 마시면서 걸어가기 (골드5)

문제 풀이 날짜: 2023.09.27
포스트 작성일: 2023.09.30

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 9205번: 맥주 마시면서 걸어가기 (골드5)

 

키워드

BFS

 

풀이 접근법

• 한 정점으로부터 다른 모든 정점을 방문할 수 있다.
  • 따라서 모든 정점을 연결하는 완전 그래프를 생성하여 풀이하였다. 
  • 이때, 편의점을 순서대로 방문하지 않아도 된다.
  • 즉, 그래프의 간선을 큰 번호 → 작은 번호 순으로도 이을 수 있게 해야 한다.
• 편의점을 방문했다면 맥주량이 복구되므로, 매 순간마다 가중치가 1000 이하(현재 보유 맥주량으로 갈 수 있는 거리)인 간선만 선택한다.
• 현재 보유중인 맥주로 다음 지점까지 갈 수 있는 경우(가중치 1000 이하)만 Queue에 넣는다. 나머지 간선은 가지치기 된다.
• 도착지점에 다다를 때까지 반복하고, 도착을 할 수 있다면 true 반환, 그 전에 탐색이 종료된다면 false를 반환한다.

 

코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {

	private static final int MAX_BEER = 20;
	private static final int UNIT_DIST = 50;
	
	private static int N;
	
	private static int start = 0;
	private static int destination;
	
	private static boolean[] visited;
	private static List<Node>[] graph;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		while(T-- > 0) {
			N = Integer.parseInt(br.readLine());
			
			graph = new LinkedList[N + 2];
			visited = new boolean[N + 2];
			destination = N + 2 - 1;
			
			for(int i = 0; i < N + 2; i++) {
				graph[i] = new LinkedList<>();
			}
			
			String[] temp;
			Point[] points = new Point[N + 2];
			for(int i = 0; i < N + 2; i++) {
				temp = br.readLine().split(" ");
				
				int x = Integer.parseInt(temp[0]);
				int y = Integer.parseInt(temp[1]);
				
				points[i] = new Point(x, y);
			}
			
			//각 정점간의 거리 계산
			for(int i = 0; i < points.length; i++) {
				Point v = points[i];
				for(int j = 0; j < points.length; j++) {
					if (i == j) continue;
					
					Point u = points[j];
					
					int dist = Math.abs(v.x - u.x) + Math.abs(v.y - u.y);
					
					graph[i].add(new Node(j, dist));
				}
			}
			
			boolean result = BFS();
			
			if(result) {
				sb.append("happy").append("\n");
			} else { sb.append("sad").append("\n"); }
		}
		
		System.out.println(sb.toString());
	}
	
	private static boolean BFS() {
		Queue<Integer> queue = new ArrayDeque<>();
		
		visited[start] = true;
		queue.add(start);
		
		while(!queue.isEmpty()) {
			int v = queue.poll();
			
			if(v == destination) { //종점이라면
				return true; //탐색 성공
			}
			
			for(Node u : graph[v]) {
				int availableDist = MAX_BEER * UNIT_DIST; //보유 맥주로 갈 수 있는 거리
				int dist = u.dist; //앞으로 가야하는 거리
				
				if(visited[u.num]) { continue; }
				
				if(availableDist >= dist) {
					visited[u.num] = true;
					queue.add(u.num);
				}
			}
		}
		
		return false;
	}

}

class Node {
	int num;
	int dist;
	
	public Node(int num, int dist) {
		this.num = num;
		this.dist = dist;
	}
}

---