아이디어

• 주어진 정보는 정점이 $N+2$개이고, 맥주병 20개($50 \times 20 = 1000$ 미터) 안에 갈 수 있는 정점끼리 연결된 그래프라고 생각한다.
  • 0번 정점은 상근이네 집, 1~$N$번 정점은 편의점, $N+1$번 정점은 펜타포트 락 페스티벌을 나타낸다.

1. 그래프 탐색을 이용한 방법

• 그래프를 표현하는 방법은 여러 가지가 있지만, 탐색을 한다면 인접 리스트로 표현하였다.
• 해당 그래프에 대해 DFS나 BFS를 이용해 0번 정점에서 $N+1$번 정점까지 갈 수 있는지 여부를 탐색하면 된다.
  • 필자는 BFS를 사용했다.
• 시간복잡도는 $O(n)$이다.

2. Floyd-Warshall 알고리즘

• $N \le 100$이므로 시간복잡도가 $O(n^3)$인 Floyd-Warshall 알고리즘도 시도해볼 수 있다.
• ok라는 2차원 boolean 배열을 만든다. 이는 두 지점 간에 이동할 수 있음을 의미한다.
• $k$번 정점을 경유해서 갈 수 있으면, 즉, ok[i][k] && ok[k][j]면 ok[i][j]를 true로 한다.

코드

1. BFS를 이용한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int T, n;
	static int[] x;
	static int[] y;
	static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
	
	public static void main(String[] args) throws Exception {
		T = Integer.parseInt(rd.readLine());
		for (int t=1; t<=T; t++) {
			n = Integer.parseInt(rd.readLine());
			
			x = new int[n+2];
			y = new int[n+2];
			for (int i=0; i<n+2; i++) {
				tk = new StringTokenizer(rd.readLine());
				x[i] = Integer.parseInt(tk.nextToken());
				y[i] = Integer.parseInt(tk.nextToken());
			}
			
			adjList.clear();
			for (int i=0; i<n+2; i++) adjList.add(new ArrayList<>());
			for (int i=0; i<n+2; i++) {
				for (int j=i+1; j<n+2; j++) {
					if (Math.abs(x[i] - x[j]) + Math.abs(y[i] - y[j]) <= 1000) { 
						adjList.get(i).add(j);
						adjList.get(j).add(i);
					}
				}
			}
			
			bfs();
		}
		System.out.println(sb);
	}
	
	static void bfs() {
		Queue<Integer> q = new ArrayDeque<>();
		boolean[] enqueued = new boolean[n+2];
		
		q.offer(0);
		enqueued[0] = true;
		
		while (!q.isEmpty()) {
			int v = q.poll();
			
			if (v == n+1) {
				sb.append("happy\n");
				return;
			}
			
			for (int n: adjList.get(v)) {
				if (enqueued[n]) continue;
				q.offer(n);
				enqueued[n] = true;
			}
		}
		sb.append("sad\n");
	}
}

2. Floyd-Warshall을 이용한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int T, n;
	static int[] x;
	static int[] y;
	static boolean[][] ok;
	
	public static void main(String[] args) throws Exception {
		T = Integer.parseInt(rd.readLine());
		for (int t=1; t<=T; t++) {
			n = Integer.parseInt(rd.readLine());
			
			x = new int[n+2];
			y = new int[n+2];
			for (int i=0; i<n+2; i++) {
				tk = new StringTokenizer(rd.readLine());
				x[i] = Integer.parseInt(tk.nextToken());
				y[i] = Integer.parseInt(tk.nextToken());
			}
			
			ok = new boolean[n+2][n+2];
			for (int i=0; i<n+2; i++) {
				for (int j=i+1; j<n+2; j++) {
					if (Math.abs(x[i] - x[j]) + Math.abs(y[i] - y[j]) <= 1000) { 
						ok[i][j] = ok[j][i] = true;
					}
				}
			}

			// floyd-warshall
			for (int k=0; k<n+2; k++) {
				for (int i=0; i<n+2; i++) {
					if (i == k) continue;
					for (int j=0; j<n+2; j++) {
						if (k == j || i == j) continue;
						ok[i][j] |= ok[i][k] && ok[k][j];
					}
				}
			}
			if (ok[0][n+1])	sb.append("happy\n");
			else			sb.append("sad\n");
		}
		System.out.println(sb);
	}
}

메모리 및 시간

• BFS
  • 메모리: 15148 KB
  • 시간: 168 ms
• Floyd-Warshall
  • 메모리: 32384 KB
  • 시간: 452 ms

리뷰

• '맥주병'이라는 요소가 헷갈리게 할 수 있는데, 알고 보면 별 거 없는 문제다.
• $n$이 작기 때문에 여러 방식으로 접근할 수 있다. 듣자 하니 Union-find 알고리즘으로 풀 수도 있다고 한다.
• 시간복잡도의 중요성을 메모리와 시간 차이로 볼 수 있다.