백준 3108 로고 (java)

접근

겹치지 않는 몇 개의 그룹이 존재하냐를 묻는 문제이다.

문제는 길지만 핵심 개념은 위와 같다.
하지만 한가지 조건이 있는게 거북이가 0,0에서 시작하는데
0,0을 지나는 사각형이 존재하는 경우는 거북이가 펜을 위로 올리는 PU 연산이 필요 없다는 것을 기억해야 한다.

과정

일단 나는 도형 문제이기 때문에
프로그래머스의 아이템 줍기 문제처럼
map을 2배로 해서 겹치는 부분에 대해서 컴퓨터가 혼란을 느끼지 않도록 설정했다.

BFS 풀이

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

public class Main{

    static boolean[][] map;
    static boolean[][] visit;

    static int[] cx = {-1,1,0,0};
    static int[] cy = {0,0,-1,1};


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());//직사각형의 개수 1~1000

        // 좌표 -500 ~ 500 총 1001
         map = new boolean[2003][2003];
         visit = new boolean[2003][2003];

         ArrayList<int[]> list = new ArrayList<>();

        for(int i=0;i<N;i++){
            StringTokenizer st =new StringTokenizer(br.readLine()," ");
            int col1 = Integer.parseInt(st.nextToken())*2+1000;
            int row1 = Integer.parseInt(st.nextToken())*2+1000;
            int col2 = Integer.parseInt(st.nextToken())*2+1000;
            int row2 = Integer.parseInt(st.nextToken())*2+1000;

            for(int j=row1;j<=row2;j++){
                map[j][col1]=true;
                map[j][col2]=true;
            }

            for(int j=col1;j<=col2;j++){
                map[row1][j]=true;
                map[row2][j]=true;
            }

            list.add(new int[]{row1,col1});

        }
        int cnt=0;
        for(int[] v : list){
            if(visit[v[0]][v[1]]==false) {
                cnt++;
                BFS(v[0],v[1]);
            }
        }


        if(visit[1000][1000]==true) cnt--;

        bw.write(Integer.toString(cnt));
        bw.flush();
        bw.close();
        br.close();



    }

    static void BFS(int start_r, int start_c) {
        Queue<int[]> Q = new LinkedList<>();
        Q.offer(new int[]{start_r,start_c});
        visit[start_r][start_c]=true;
        while(!Q.isEmpty()){
            int size = Q.size();
            for(int i=0;i<size;i++){
                int[] q = Q.poll();
                //상하좌우 이동
                for(int j=0;j<4;j++){
                    int r = cx[j]+q[0];
                    int c = cy[j]+q[1];

                    if(r<0 || r>=2003 || c<0 || c>=2003) continue;

                    if(map[r][c]==true && visit[r][c]==false){
                        Q.offer(new int[]{r,c});
                        visit[r][c]=true;
                    }
                }

            }


        }

    }


}

다른 풀이

일단 map을 2배로 만드는게 맞을까라는 의문이 들어서 다른 사람의 풀이를 찾아보니 union&find로 접근한 풀이가 있었다.

힌트를 얻고 다시 풀어보았다.

대략적인 접근은 이러할거 같다
1. row와 column에 대한 정보로 겹치는지 확인
이 1번에서 범위 설정 부분에서 조금 복잡하다.
2. 겹치면 같은 부모를 갖는다.
3. 겹치지 않으면 다른 부모
4. 부모 수를 세고
5. 만약 도형 중에 0,0을 지나는게 존재하면 -1