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

 

 

[문제]

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

 

 

[소스 코드]

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int t = Integer.parseInt(br.readLine());
		for(int tc=1;tc<=t;tc++) {
			int n = Integer.parseInt(br.readLine());
			int[][] stores = new int[n+2][2];
			for(int i=0;i<n+2;i++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				stores[i][0] = x;
				stores[i][1] = y;
			}
			boolean[] visit = new boolean[n+2];
			Queue<Integer> q = new LinkedList<>();
			q.offer(0);
			boolean result = false;
			while(!q.isEmpty()) {
				int curr = q.poll();
				if(curr==n+1) {
					result = true;
					break;
				}
				for(int i=1;i<n+2;i++) {
					if(!visit[i]) {
						int dist = Math.abs(stores[curr][0] - stores[i][0]) + Math.abs(stores[curr][1] - stores[i][1]);
						if(dist<=1000) {
							visit[i] = true;
							q.offer(i);
						}
					}
				}
			}
			if(result) System.out.println("happy");
			else System.out.println("sad");
		}
	}
}