문제 : https://www.acmicpc.net/problem/9025

Key Points

편의점의 위치가 상근이네 집 즉 출발점과 가까운 위치에 있는 것이 아니라 일일히 확인해봐야 한다.
그 말은 모든 경우를 다 해봐야 하는 것이다. 즉, BFS로 문제를 접근해서 풀어야 한다.

Explain

  1. 시작위치, 편의점위치, 도착지의 좌표 모두 클래스 배열인 location[]에 넣어준다.
  2. 시작위치로부터 출발한다. (큐에 넣어준다.)
  3. 출발하여 location[] 클래스 배열 안에 있는 조건에 맞는 좌표를 방문한다.
  4. 조건은 출발위치로부터 다음 위치의 차이가 1000이하이고, 방문하지 않은 점이어야 한다.
  5. 페스티벌 위치 즉 도착지와 계속 비교하면서 페스티벌 위치라면 즉시 boolean success를 true로 변경하고 빠져나온다.
  6. boolean success에 따라 결과를 출력하면 된다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class Exam9205 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// 모든 경우를 다 해보는 BFS 문제

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int test_case = Integer.parseInt(bf.readLine());
		// 테스크 케이스 입력

		for(int i=0;i<test_case;i++) {
			int N = Integer.parseInt(bf.readLine());
			LOCATION[] location = new LOCATION[N+2]; // 모든 위치의 좌표를 저장하기 위한 클래스 배열
			int[] check = new int[N+2]; // 방문했는지 안했는지 확인하기 위한 배열
			Queue<LOCATION> q = new LinkedList<LOCATION>();
			boolean success = false; // 도착지에 도달하면 true로 바꾼다.
			
			for(int j=0;j<N+2;j++) {
				StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
				location[j] = new LOCATION(Integer.parseInt(st.nextToken())
						,Integer.parseInt(st.nextToken()));
				
			}
			
			// 입력 끝
			LOCATION start = location[0]; // 출발지점
			LOCATION end = location[N+1]; // 도착지점
			
			q.add(start); // 큐에 넣는다. 
			
			while(!q.isEmpty()) {
				LOCATION current = q.poll(); // 삭제하면서 원소를 뺀다.
				if(current.equals(end)) { // 도착지점에 도착하면 success를 true로 바꾸고 탈출
					success = true;
					break;
				}
				
				for(int j=1;j<N+2;j++) {
					if(check[j] == 0 && Math.abs(current.x - location[j].x) + 
							Math.abs(current.y - location[j].y) <=1000) {
								// 조건 : 방문하지 않았고, 좌표의 차이가 1000이하인 것들만 큐에 저장한다.
						q.add(location[j]); // 큐에 넣는다.
						check[j] = 1; // 방문했음을 표시
					}
				}
			}
			
			if(success)
				System.out.println("happy");
			else
				System.out.println("sad");
			
		}
		
		
	}
}
// 좌표를 저장하는 클래스 배열
class LOCATION{
	int x;
	int y;
	
	LOCATION(int x, int y){
		this.x = x;
		this.y = y;
	}
}