[BOJ] 3108 로고 Java 풀이

 

 

BOJ 3108 로고

 

문제를 보고 처음 한 것은 예제 입력을 직접 그려보는 것이었다.  직사각형이 여러개 그려지는 모습이 머릿속에서 잘 안그려졌기 때문..

그리다가 x, y를 바꿔 그려 다시 그리면서 너무 더러워졌다.... 붉은색으로 입력받은 직사각형을 하나하나 그려주고 번호를 매겨줬다.

???... 겹쳐서 그려지는 직사각형이 있다.

문제에서 펜을 떼는 PU 명령의 최솟값을 구하라고 했고, 거북이가 같은 선을 여러번 그릴 수 있다고 했다. 펜을 떼지 않고 그릴 수 있는 직사각형들은 떼지 않고 그리고, 떼는 횟수를 구하면 될 것 같다.

근데 떼지 않고 그릴 수 있는 직사각형의 정보를 어떻게 담지.. 고민하다 먼저 생각이 든 것은 그려야 하는 좌표들을 Set에 모두 담아두는 것이었다. Set을 생각한 이유는 겹치는 부분들은 중복해서 넣어둘 필요가 없으니까.. 그리고 Set에 그려야하는 점들을 모두 담아주고 나서 x, y순으로 정렬한 뒤에, (0, 0)에서 시작해 Set에 들어있는 점 중 x(수직)이동, y(수평)이동이 가능한 점들을 찾아 거북이를 작동시켜주면 되겠다. 거북이는 클래스를 만들어서 메소드 정의해주고 움직여주면 되겠지..? 근데... 너무 복잡하다...

좌표 크기가 -500부터 +500인데, 직사각형의 개수가 1000개가 주어지는데 점마다 거북이 행동을 결정하면.. Set에 있는 좌표를 진행시키는 것도 방문처리를 포함해 수직이동이나 수평이동을 생각할 때 x가 같은 것만 아니라 y가 같은 좌표도 고려해야하는데.. 시간 초과의 향기가 너무 많이난다.

다시 생각해본다. 펜을 떼는 횟수만 구하면 된다. 직사각형들이 주어지고, 펜을 떼지 않고 그릴 수 있는 사각형은 한번에 그린다. 

직사각형 중 접점이 있는 사각형끼리 하나의 집합으로 묶어주면 된다.

접점이 있는 사각형은 무엇일까?
1) 한 직사각형 안에 완전히 내포되어 있는 관계가 아닐 것
2) 좌우상하 방향으로 아예 떨어져 있는 관계일 것(x2보다 x1이 더 크거나, 반대로 x1보다 x2가 더 작거나..)

하나 더 고려할 점은 시작점 (0, 0)에서 펜을 내린 상태로 시작하기 때문에, (0,0)을 지나지 않는 경우 반드시 펜을 떼고 시작하게 되기 때문에 이에 대한 처리가 필요하다. (0,0)과 접점이 있는 사각형은 별도 처리하지 않기 위해 미리 (0,0,0,0)으로 넣어놓고 입력받은 직사각형들을 접접이 있는지 검사해보면 되지 않을까?

그대로 코드로 구현해서 구현하면 정답 결과를 받을 수 있다.

구현 - BFS

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 접점이 있는 사각형끼리는 펜을 떼지 않고 한 번에 그릴 수 있으므로, 접점이 없는 사각형 집합의 갯수를 구함.
public class P3108 {
	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 Exception{
		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);
	}
	
	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가 N을 내포하는 경우 
				|| (c.x1 > n.x1 && n.x2 > c.x2 && c.y1 > n.y1 && n.y2 > c.y2) // N이 C를 내포하는 경우
				|| c.x2 < n.x1 || c.x1 > n.x2 || c.y2 < n.y1 || c.y1 > n.y2)	// 아예 접점이 없는 경우
		{
			return false;}
		
		
		// C와 N이 공유하는 부분이 있는 경우
			
		return true;
	}

}


class Rec {
	int x1, x2, y1, y2;

	public Rec(int x1, int y1, int x2, int y2) {
		this.x1 = x1;
		this.y1 = y1;
		this.x2 = x2;
		this.y2 = y2;
		
	}

	@Override
	public String toString() {
		return "Rec [x1=" + x1 + ", x2=" + x2 + ", y1=" + y1 + ", y2=" + y2 + "]";
	}
}

 

 

풀이 방식만 캐치하면 구현 과정에서 크게 어려운 점은 없지만 그 풀이 방식을 캐치하는 것이 좀처럼 쉽지 않다. 처음 거북이를 직접 구현하려다 잘못된 낌새를 느끼는 것 까지는 갔지만, 문제를 재정의하는 과정에서 해결하지 못했다. 완전구현 카테고리에 있어 문제가 단순할 거라는 예상보다 대부분 훨씬 어려움을 겪고 있다. 이전에 다뤘던 개념 없이 그냥 문제를 코드로 구현하는 문제라기보다는 이전에 배웠던 개념을 다양하게 문제에 적용해 코드로 변환하는 섹션으로 느껴진다. 

구현 참고 블로그 : jaejin89.tistory.com/19

여튼, 위처럼 BFS 방식으로 Queue를 이용해서 문제를 해결할 수 있는데, 문제 풀이를 계속 보다보니 입력 받은 직사각형중에  접점이 있는 직사각형을 계속해서 찾아나간다는 점에서 BFS보다는 DFS가 연상됐다. 그래서 DFS로도 도전해보게 되었는데....

DFS로 구현해보니, 결과적으로 직사각형들을 접점이 있는 것끼리 집합으로 묶고, 집합의 개수를 출력해야하는데 생각하지 못했는데 집합의 개수를 세는 것이 골치아팠다. 결국 어떤 집합에 속하는지를 나타내는 flag를 별도로 넣어서 구현해봤다.

그런데.. 동일한 로직인데 오답을 받게 되었고, 결국 혼자서는 틀린 이유를 찾지 못해 BOJ에 질문글을 작성했다..ㅠㅠ
이유를 찾으면 다시 여기 수정해서 올려야지!

DFS 풀이 - 오답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P3108_2 {
	static int N, cnt, flags[]; 
	static Info_P3108_2[] recs;
	static boolean[] visited;
	
	private static void dfs(int start, int flag) {
		
		// 방문하지 않은 경우에만 수행
		if(visited[start]) {
			return; 
		}
		
		visited[start] = true;
		flags[start] = flag;
		
		for(int i = 0; i <= N; i++) {
			// 현재 사각형과 접점이 있다면 간다.
			// 비교 대상은 1) 자기 자신 제외, 2) 방문 X
			if(start != i && !visited[i]) {
				// 접점이 있는지 확인
				if(check(start, i)) {
					dfs(i, flag);
				}
			}
		}
	}
	
	private static boolean check(int rec1, int rec2) {
		Info_P3108_2 r1 = recs[rec1];
		Info_P3108_2 r2 = recs[rec2];
		
		// r1이 r2를 내포하는 경우 => 접점 존재 X
		if(r1.x1 < r2.x1 && r2.x2 < r1.x2 && r1.y1 < r2.y1 && r2.y2 < r1.y2) {
			return false;
		}
		// r2가 r1을 내포하는 경우 => 접점 존재 X
		if(r2.x1 < r1.x1 && r1.x2 < r2.x2 && r2.y1 < r1.y1 && r1.y2 < r2.y2) {
			return false;
		}
		// 접점이 존재하지 않는 경우
		if(r1.x2 < r2.x1 || r1.y2 < r2.y1 || r2.x2 < r1.x1 || r2.y2 <r1.y1) {
			return false;
		}
		
		
		// 접점이 반드시 존재
		return true;
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		recs = new Info_P3108_2[N+1];
		visited = new boolean[N+1];
		flags = new int[N+1];
		
		// 원점을 지나거나 포함하는 경우 처리하기 위해 미리 넣어놓음
		recs[0] = new Info_P3108_2(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());
			Info_P3108_2 rec = new Info_P3108_2(x1, y1, x2, y2);
			recs[i] = rec;
		}
		
		for(int i = 0; i <= N; i++) {
			dfs(i, i);
		}
		// Set이 다른 개수를 계산
		for(int i = 0; i < N; i++) {
			if(flags[i] != flags[i+1]) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}

}


class Info_P3108_2{
	int x1, y1, x2, y2;

	public Info_P3108_2(int x1, int y1, int x2, int y2) {
		this.x1 = x1;
		this.y1 = y1;
		this.x2 = x2;
		this.y2 = y2;
	}
	@Override
	public String toString() {
		return "[x1=" + x1 + ", y1=" + y1 + ", x2=" + x2 + ", y2=" + y2 + "]";
	}
}