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

문제 출처: www.acmicpc.net/problem/9205

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

: 집과 도착지 그리고 편의점을 하나의 배열에 저장한다.

: 집을 먼저 큐에 넣어주고 편의점들과 도착지를 검사하면서 맥주 20병 내로 이동할 수 있는 곳들을 찾아

: BFS 방식으로 이동시키고 도착지에 도달할 수 있으면 happy 를 도착하지 못하고 끝나면 sad를 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static class Point{
		int x, y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "Point [x=" + x + ", y=" + y + "]";
		}
		
		
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 0; tc < T; tc++) {
			int N = Integer.parseInt(br.readLine());
			
			Point[] point = new Point[N+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());
				point[i] = new Point(x, y);
			}
//			System.out.println(Arrays.toString(point));
			boolean flag = false;
			boolean[] v = new boolean[N+2];
			Queue<Point> q = new LinkedList<>();
			q.offer(point[0]);
			v[0] = true;
			while(!q.isEmpty()) {
				Point p = q.poll();
				if(p.x == point[N+1].x && p.y == point[N+1].y) {
					flag = true;
					break;
				}
				for(int i = 1; i < N+2; i++) {
					int dx = Math.abs(point[i].x - p.x);
					int dy = Math.abs(point[i].y - p.y);
					if(v[i] || dx + dy > 1000) continue;
					q.offer(point[i]);
					v[i] = true;
				}
			}
			if(flag) sb.append("happy\n");
			else sb.append("sad\n");
		}
		System.out.println(sb);
	}
}