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

DFS문제로 풀었습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main9205_맥주마시면서걸어가기 {
    private static Pair[] position;
    private static int n;
    private static boolean[] visited;
    private static boolean flag;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        for (int testCase = 0; testCase < T; testCase++) {
            n = Integer.parseInt(br.readLine().trim());
            position = new Pair[n + 2];
            visited = new boolean[n + 2];
            for (int i = 0; i < n + 2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                position[i] = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), i);
            }
            visited[0] = true;
            flag = false;
            dfs(position[0].x, position[0].y, position[0].idx);
            if (flag == true) {
                System.out.println("happy");
            } else {
                System.out.println("sad");
            }
        }
    }
    public static void dfs(int x, int y, int idx) {
        if (x == position[n + 1].x && y == position[n + 1].y) {
            flag = true; //마지막 지점에 도착했을 때 
            return;
        } else {
            for (int i = 0; i < n + 2; i++) {
                int distance = Math.abs(x - position[i].x) + Math.abs(y - position[i].y);
                if (flag)
                    return;
                if (idx != i) { // 자기 자신에 대해서 검사하는 부분 제외시켜줌.
                    if (!visited[i] && distance <= 1000) {
                        visited[i] = true;
                        dfs(position[i].x, position[i].y, position[i].idx);
                    }
                }
            }
        }
    }
    static class Pair {
        int x;
        int y;
        int idx;
        public Pair(int x, int y, int idx) {
            super();
            this.x = x;
            this.y = y;
            this.idx = idx;
        }
    }
}