문제 출처
https://www.acmicpc.net/problem/3108
3108번: 로고
문제 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 각도로 표현할 수 있다. 거북이는 입에 연필을 물고 있는데, 연필을 내리면 움직일 때 화면에 선을 그리고, 올리면 선을 그리지 않고 그냥 지나가기만 한다. 제일 처음에 거북이는 (0,0)에 있고, 거북이가 보고 있는 방향은 y축이 증가하는 방향이다. 또한 연필은 내
www.acmicpc.net
접근 방식 및 풀이
- 어떻게 접근 해야할 지 도저히 감이 안와서.. 처음부터 다른 블로그를 참고했다.
- 참고 : 백준 3108. 로고 :: 돼지개발자
소스 코드
|
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N;
static Rec[] map;
static boolean[] visited;
static Queue<Integer> q = new LinkedList<>();
static int cnt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new Rec[N+1];
visited = new boolean[N+1];
map[0] = new Rec(0,0,0,0);
for (int i = 1; i <= N ; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
map[i] = new Rec(x1,y1, x2, y2);
}
for (int i = 0; i <= N ; i++) {
if(visited[i]) continue;
visited[i] = true;
q.add(i);
while (!q.isEmpty()){
int cur = q.poll();
for (int j = 0; j <=N ; j++) {
if(cur==j || !check(cur, j) || visited[j]){
continue;
}
visited[j] = true;
q.add(j);
}
}
cnt++;
}
System.out.println(cnt-1);
}
private static boolean check(int cur, int next) {
Rec c = map[cur];
Rec n = map[next];
if((c.x1 < n.x1 && n.x2 < c.x2 && c.y1 < n.y1 && n.y2 < c.y2)
|| (c.x1 > n.x1 && n.x2 > c.x2 && c.y1 > n.y1 && n.y2 > c.y2)
|| c.x2 < n.x1 || n.x2 < c.x1 || c.y2 < n.y1 || n.y2 < c.y1){
return false;
}
return true;
}
}
class Rec{
int x1;
int y1;
int x2;
int y2;
public Rec(int x1, int y1, int x2, int y2) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}
}
|
결과
'Competition > Baekjoon' 카테고리의 다른 글
| [백준] 9019번 자바 DSLR (0) | 2020.05.11 |
|---|---|
| [백준] 2632번 자바 피자 (0) | 2020.05.10 |
| [백준] 2580번 자바 스도쿠 (0) | 2020.05.10 |