[JAVA] BOJ 백준 9205 맥주 마시면서 걸어가기

https://www.acmicpc.net/problem/9205

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

💡 DFS, BFS, 다익스트라, 플로이드 워셜 알고리즘 모두로 풀 수 있는 문제이다.

나는 BFS를 제외한 세가지 방법으로 문제를 풀었다.

📌 Floyd Warshall 알고리즘 이용

1. 이차원 배열 places에 집, 편의점, 페스티벌의 위치를 저장한다.
2. 이차원 배열 D에 경유지 없이 걸어야하는 최대 거리를 저장한다. (경유지 = 편의점)
3. beer()에서 Floyd 알고리즘으로 D의 값을 갱신한다.
4. 이때 집부터 페스티벌 사이의 D값이 1000을 넘는다면 맥주가 부족하기 때문에 false를 아니면 true를 반환한다.

import java.io.*;
import java.util.*;

public class BOJ_9205_floyd {
	static int[][] places, D;
	static int n;
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(bf.readLine());
		for(int t=1; t<=T; t++) {
			n = Integer.parseInt(bf.readLine());
			places = new int[n+2][2];
			D = new int[n+2][n+2]; // 마지막으로 맥주를 구매한 곳으로부터 페스티벌까지의 거리
			for(int i=0; i<n+2; i++) {
				StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
				places[i][0] = Integer.parseInt(st.nextToken());
				places[i][1] = Integer.parseInt(st.nextToken());
			}
			for(int i=0; i<n+2; i++) {
				for(int j=i+1; j<n+2; j++) {
					D[i][j] = Math.abs(places[i][0]-places[j][0])+Math.abs(places[i][1]-places[j][1]);
					D[j][i] = D[i][j];
				}
			}
			System.out.println(beer() ? "happy" : "sad");
		}
	}
	static boolean beer() {
		for(int k=1; k<=n; k++) {
			for(int i=0; i<n+1; i++) {
				for(int j=1; j<n+2; j++) {
					if(k == i || k == j || i == j) continue;
					if(D[i][k] <= 1000 && D[k][j] < D[i][j])
						D[i][j] = D[k][j];
				}
			}
		}
		if(D[0][n+1] <= 1000) return true;
		return false;
	}
}

beer()의 3중 for문을 보면 k, i, j중 같은 값이 존재하는 경우 D를 갱신하지 않아도 항상 최소값인 0이 들어가게 된다.

경유지를 중간에 만나게 되면 1. (출발지에서 경유지까지 거리가 1000이하)이고 2. (경유지부터 도착지까지 거리)가 < (출발지부터 도착지까지 거리)보다 작다면 값을 갱신한다.

📌 Dijkstra 알고리즘 이용

1. 마찬가지로 places배열에 위치 값을 저장한다.
2. 이번엔 일차원 배열 D에 출발지부터 각 위치까지의 거리를 저장한다. 
(이때, 경유지를 거쳐가는 경우 각 거리가 1000이하일때만 값을 수정해준다. 안 거쳐가는 경우도 마찬가지)
3. D[페스티벌]의 값이 초기값으로부터 갱신되지 않았다면 1000이하의 경유지를 거쳐 도착하는 경우가 없다는 뜻이므로 "sad"반환

import java.io.*;
import java.util.*;

public class BOJ_9205_Dijkstra {
	static int[][] places;
	static int[] D;
	static int n;
	static class Node{
		int to;
		int weak;
		Node link;
		public Node(int to, int weak, Node link) {
			super();
			this.to = to;
			this.weak = weak;
			this.link = link;
		}
	}
	static Node[] nodes;
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(bf.readLine());
		for(int t=1; t<=T; t++) {
			n = Integer.parseInt(bf.readLine());
			places = new int[n+2][2];
			for(int i=0; i<n+2; i++) {
				StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
				places[i][0] = Integer.parseInt(st.nextToken());
				places[i][1] = Integer.parseInt(st.nextToken());
			}
			
			nodes = new Node[n+2];
			for(int i=0; i<n+2; i++) {
				for(int j=i+1; j<n+2; j++) {
					if(i == j) continue;
					int weak = Math.abs(places[i][0]-places[j][0])+Math.abs(places[i][1]-places[j][1]);
					if(weak <= 1000) {
						nodes[i] = new Node(j, weak, nodes[i]);
						nodes[j] = new Node(i, weak, nodes[j]);
					}
				}
			}
			
			D = new int[n+2];
			Arrays.fill(D, 987654321);
			PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));
			D[0] = 0;
			pq.offer(new int[] {0, 0});
			while(!pq.isEmpty()) {
				int[] now = pq.poll();
				if(now[1] > D[now[0]]) continue;
				for(Node n = nodes[now[0]]; n!= null; n = n.link)  {
					if(D[n.to] > now[1] + n.weak) {
						D[n.to] = now[1] + n.weak;
						pq.offer(new int[] {n.to, D[n.to]});
					}
				}
			}
			
			System.out.println(D[n+1] == 987654321 ? "sad" : "happy");
		}
	}
}

자세히 보자

D = new int[n+2];
Arrays.fill(D, 987654321);
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));
D[0] = 0;
pq.offer(new int[] {0, 0});
while(!pq.isEmpty()) {
	int[] now = pq.poll();
	if(now[1] > D[now[0]]) continue;
	for(Node n = nodes[now[0]]; n!= null; n = n.link)  {
		if(D[n.to] > now[1] + n.weak) {
			D[n.to] = now[1] + n.weak;
			pq.offer(new int[] {n.to, D[n.to]});
		}
	}
}

System.out.println(D[n+1] == 987654321 ? "sad" : "happy");

1. D 배열 선언
2. D에 초기값을 준다.
3. 우선순위 큐에 출발지로부터 거리가 짧은 순서대로 정렬할 수 있게 한다.
4. 초기값은 출발지로 설정한다. 이때 출발지로부터 출발지까지 거리는 0이다.
5. now[1] = 출발지부터 now[0]까지 거리
6. D[현재 위치] < now[1]인 경우 now[0]의 최단거리가 새롭게 갱신되었기 때문에 이 값으로 다른 값들을 갱신하지 않아도 된다.
7. 그것이 아니라면 현재 위치로부터 1000이하로 갈 수 있는 값들을 갱신한다.

📌 DFS 이용

1. places와 D의 초기값은 Floyd와 동일하다.
2. visited를 이차원 배열로 선언하여 출발지로부터 도착지(경유지)까지의 조사가 완료되었는지 확인하게 한다.
3. dfs(x)는 x를 출발지로 할 때 n+1(도착지)까지 맥주를 마시며 도착할 수 있는지를 반환한다.
4. x가 n+1에 도착한다면 가능하다는 의미이므로 true를 반환
5. for문을 통해 1부터 n+1까지 조사하면서 조사하지 않은 길이고 거리가 1000이하이면 갈 수 있기 때문에 dfs를 재귀호출한다.

import java.io.*;
import java.util.*;

public class BOJ_9205_dfs{
	static int[][] places, D;
	static int n;
	static boolean[][] v;
	static boolean flag;
	
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(bf.readLine());
		for(int t=1; t<=T; t++) {
			n = Integer.parseInt(bf.readLine());
			places = new int[n+2][2];
			D = new int[n+2][n+2];
			for(int i=0; i<n+2; i++) {
				StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
				places[i][0] = Integer.parseInt(st.nextToken());
				places[i][1] = Integer.parseInt(st.nextToken());
			}
			for(int i=0; i<n+2; i++) {
				for(int j=i+1; j<n+2; j++) {
					D[i][j] = Math.abs(places[i][0]-places[j][0])+Math.abs(places[i][1]-places[j][1]);
					D[j][i] = D[i][j];
				}
			}
			v = new boolean[n+2][n+2];
			flag = false;
			System.out.println(dfs(0) ? "happy" : "sad");
		}
	}
	static boolean dfs(int x) {
		if(flag) return true;
		if(x == n+1) {
			flag = true;
			return true;
		}
		boolean flag = false;
		for(int i=n+1; i>=1; i--) {
			if(i == x || v[x][i] || D[x][i] > 1000) continue;
			v[x][i] = true;
			flag |= dfs(i);
			
		}
		return flag;
	}
}