백준_맥주 마시면서 걸어가기_9205

알고리즘

1. 시작좌표부터 편의점좌표, 도착좌표까지 갈 수 있는 거리가 1000미터 이기 때문에

   거리가 1000이하인 곳의 인접리스트를 만들어야 함.

2. 인접리스트와 방문배열을 이용하여 시작좌표를 기준으로 dfs를 돌려 도착좌표에 도달하면 정답 출력.

※ 주어진 좌표를 인접리스트로 만드는게 핵심임. (2차원 배열로 표시했다가는 메모리 초과가 날 듯..)

 

 

import java.util.ArrayList;
import java.util.Scanner;

public class 맥주마시면서걸어가기_9205 {
	static int T, n, ans;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {

			n = sc.nextInt();

			int[][] map = new int[n + 2][2];
			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < 2; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			
			ArrayList<Integer>[] list = new ArrayList[n+2];
			for (int i = 0; i < list.length; i++) {
				list[i] = new ArrayList<Integer>();
			}
			
			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map.length; j++) {
					if(i==j) continue;
					if(Math.abs(map[i][0] -map[j][0]) + Math.abs(map[i][1] -map[j][1]) <=1000) {
						list[i].add(j);
					}
				}
			}
			boolean[] v= new boolean[n+2];
			v[0] =true;
			dfs(0,list,v);
			
			
			System.out.println(ans > 0 ? "happy":"sad");
			ans = 0;

//			print(map);
		}


	}

	private static void dfs(int idx, ArrayList<Integer>[] list, boolean[] v) {
		
		
		if(idx == n+1) {
			ans++;
			return;
		}
		int size = list[idx].size();
		for (int i = 0; i < size; i++) {
			 int num = list[idx].get(i);
			 if(!v[num]) {
				 v[num] = true;
				 dfs(num,list,v);			 }
		}
		
		
	}

	private static void print(int[][] map) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < 2; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

}