백준 9205. 맥주 마시면서 걸어가기 문제풀이 자바 JAVA

11
22
30 0
4200 600
5800 300
61000 1000

1BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
2List<Boolean> result = new ArrayList<>();
3
4int t = Integer.parseInt(br.readLine());
5
6for (int i = 0; i < t; i++) {
7    nodes = new ArrayList<>();
8    check = new HashSet<>();
9    flag = false;
10
11    int n = Integer.parseInt(br.readLine());
12
13    for (int j = 0; j < n + 2; j++) {
14        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
15        int tempX = Integer.parseInt(st.nextToken());
16        int tempY = Integer.parseInt(st.nextToken());
17
18        nodes.add(new Info(tempX, tempY));
19    }
20    goal = nodes.get(nodes.size() - 1);
21
22    DFS(nodes.get(0));
23    result.add(flag);
24
25    nodes.clear();
26}

1import java.io.BufferedReader;
2import java.io.IOException;
3import java.io.InputStreamReader;
4import java.util.*;
5
6public class Main {
7	static Info goal;
8	static ArrayList<Info> nodes;
9	static HashSet<Info> check;
10
11	public static void main(String[] args) throws IOException {
12		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
13		List<Boolean> result = new ArrayList<>();
14
15		int t = Integer.parseInt(br.readLine());
16
17		for (int i = 0; i < t; i++) {
18			nodes = new ArrayList<>();
19			check = new HashSet<>();
20			flag = false;
21
22			int n = Integer.parseInt(br.readLine());
23
24			for (int j = 0; j < n + 2; j++) {
25				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
26				int tempX = Integer.parseInt(st.nextToken());
27				int tempY = Integer.parseInt(st.nextToken());
28
29				nodes.add(new Info(tempX, tempY));
30			}
31			goal = nodes.get(nodes.size() - 1);
32
33			DFS(nodes.get(0));
34			result.add(flag);
35
36			nodes.clear();
37		}
38
39		for (Boolean r : result) {
40			System.out.println(r ? "happy" : "sad");
41		}
42	}
43
44	static boolean flag;
45
46	private static void DFS(Info currentNode) {
47		if (flag) return;
48		if (check.contains(currentNode)) return;
49		if (currentNode.equals(goal)) {
50			flag = true;
51			return;
52		}
53		check.add(currentNode);
54
55		int x = currentNode.getX();
56		int y = currentNode.getY();
57
58		for (Info toGo : nodes) {
59			// 현재 거리보다 목표에서 더 멀어지는 경우는 가지 말아야 할까?
60			// 돌아서 가는 경우도 있지 않을까?
61
62			if (toGo.equals(currentNode)) continue;
63
64			int toX = toGo.getX();
65			int toY = toGo.getY();
66
67			int length = Math.abs(toX - x) + Math.abs(toY - y);
68
69			if (length <= 1000) {
70				DFS(toGo);
71			}
72		}
73	}
74
75	private static class Info {
76		int x;
77		int y;
78		public Info(int x, int y) {
79			this.x = x;
80			this.y = y;
81		}
82
83		public int getX() {
84			return x;
85		}
86
87		public int getY() {
88			return y;
89		}
90	}
91}