[백준] 3108번 로고

N개의 직사각형을 그리는 필요한 PU명령의 최솟값을 출력한다!

이삭이가 BFS를 이용해서 컬러링을 해보려했다는 것에서 아이디어를 얻어 풀었던 문제다.

일반적인 BFS로 풀경우 하나의 직사각형안에 겹치지 않게 딱맞게 직사각형이 들어갈 경우 겹친다고 체크하는 문제가 발생한다.

나는 직사각형을 그리면서 겹칠 경우 FindSet을 이용해 집합을 확인하고, 같은 집합이 아닐 경우 ans에서 1을 빼주도록 구현했다.

가운데 영점이 존재하는 좌표계이기 때문에 500을 더해서 배열에 저장할 수 있도록 했다.

[문제 출처] 백준 3108번 : 로고

풀이 방법

1. Input과정에서 직사각형의 꼭짓점을 왼쪽상단과 오른쪽하단으로 저장한다.

2. 각각 다른 번호로 테두리를 그리면서 다른 직사각형의 번호를 만날 경우.

   2-1. findSet을 이용해 집합을 확인하여 다른 집합일 경우 ans에서 1을 빼주고 Union시킨다.

   2-2. 영점 (배열에서는 500, 500) 일 경우 zero 체크를 해준다.

3. zero체크가 되어있을 경우 시작부터 그릴수 있으므로 -1을 해준다.

import java.io.*;
import java.util.*;

public class Main {
	public static class Square {
		int x1, x2, y1, y2;

		public Square(int x1, int x2, int y1, int y2) {
			this.x1 = (x1 < x2)? x1 : x2;
			this.x2 = (x1 < x2)? x2 : x1;
			this.y1 = (y1 < y2)? y1 : y2;
			this.y2 = (y1 < y2)? y2 : y1;
		}
	}
	
	public static int findSet(int x) {
		if (x == p[x]) return x;
		return p[x] = findSet(p[x]);
	}
	
	public static void union(int x, int y) {
		p[findSet(y)] = findSet(x);
	}
	
	public static final int SIZE = 1001;
	public static final int PLUS = 500;
	public static int N, num, ans;
	public static boolean zero;
	public static int[][] map;
	public static int[] p;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		map = new int[SIZE][SIZE];
		p = new int[SIZE];
		for (int i = 0; i < SIZE; i++) {
			p[i] = i;
		}
		
		ans = N;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken())+PLUS; 
			int y1 = Integer.parseInt(st.nextToken())+PLUS; 
			int x2 = Integer.parseInt(st.nextToken())+PLUS; 
			int y2 = Integer.parseInt(st.nextToken())+PLUS; 
			num++;
			setSquare(new Square(x1, x2, y1, y2));
		}
		
		if (zero) ans--;
		System.out.println(ans);
	}
	
	public static void setSquare(Square square) {
		boolean flag = true;
		for (int i = square.y1; i <= square.y2; i++) {
			if (map[square.x1][i] != 0 && map[square.x1][i] != num) {
				if (findSet(map[square.x1][i]) != findSet(num)) {
					ans--;
					union(map[square.x1][i], num);
				}
			}
			if (map[square.x2][i] != 0 && map[square.x2][i] != num) {
				if (findSet(map[square.x2][i]) != findSet(num)) {
					ans--;
					union(map[square.x2][i], num);
				}
			}
			map[square.x1][i] = num;
			map[square.x2][i] = num;
			
			zeroCheck(square.x1, i);
			zeroCheck(square.x2, i);
		}
		
		for (int i = square.x1; i <= square.x2; i++) {
			if (map[i][square.y1] != 0 && map[i][square.y1] != num) {
				if (findSet(map[i][square.y1]) != findSet(num)) {
					ans--;
					union(map[i][square.y1], num);
				}
			}
			if (map[i][square.y2] != 0 && map[i][square.y2] != num) {
				if (findSet(map[i][square.y2]) != findSet(num)) {
					ans--;
					union(map[i][square.y2], num);
				}
			}
			map[i][square.y1] = num;
			map[i][square.y2] = num;
			
			zeroCheck(i, square.y1);
			zeroCheck(i, square.y2);
		}
	}
	
	public static void zeroCheck(int x, int y) {
		if (x == 500 && y == 500) zero = true;
	}
}

시간제한	메모리 제한	시간	메모리	레벨	풀이 당시 정답율
1초	128MB	104ms	18476KB	골드 3	26.47%