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

[문제]

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

 

 

[소스 코드]

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

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