BOJ G2 2108 로고 JAVA

3108번: 로고

---

문제 읽기

일단 처음 딱 문제를 읽었을 때는.. 복잡하게 여러 연산이 있는 것처럼 나왔지만 결국엔 직사각형의 연결 컴포넌트 개수를 구하는 문제라는 생각이 들었다. 다음 그림을 보면 쉽게 이해할 수 있을 것이다.

 

그래서 이를 이용해서 문제를 해결했다.

---

문제 풀기

처음에 풀이 과정을 다음과 같이 구상했다.

 

다시 정리해 보면 다음과 같다.

1. 사각형 좌표를 입력 받아 사각형 정보를 배열에 저장한다.
2. 모든 사각형을 맵에 그려준다. 사각형을 그린다는 것은 맵에 각 방향에 대해 이동 가능 여부 정보를 담아 준다는 것이다. 즉, 사각형 직선 방향에 대해 이동 가능 하다고 표시한다.
3. 첫 번째 사각형부터 시작해서 DFS 또는 BFS를 한다(둘 중 아무거나 상관 없다.) 완탐을 수행하며 지나는 점은 다 visited 배열에 표시한다.
   1. 그 다음 사각형도 visited하지 않았다면 완탐을 수행한다.
   2. 이를 통해 연결된 사각형의 컴포넌트 개수를 구할 수 있다.
4. (컴포넌트 개수 -1) + (시작 지점 방문 여부)에 따라 정답을 출력한다.
   1. 시작 지점이 정해져 있고, 시작 시 연필을 내리고 있기 때문에, 사각형을 다 돌았을 때 시작 지점도 포함되어 있다면 연필을 굳이 올려서 사각형까지 이동할 필요가 없다. 즉, 시작 지점 방문 여부에 따라 다음과 같이 더해줄 수 있다
      1. 시작 지점 방문함 : +0
      2. 시작 지점 방문 안 함 : +1

이러한 과정을 통해 코드를 작성할 수 있다.

---

실수한 부분

상하좌우 좌표

기존에 bfs, dfs를 수행할 때에는 좌표 축이 왼쪽 위에서부터 시작했다. 하지만 이 문제의 경우에는 실제 수학에서 많이 쓰는 좌표 축으로, 왼쪽 아래에서 시작한다. 그래서 상하좌우를 나타내는 dr, dc 배열의 값이 다르다는 것을 간과했다! 예제 3번이 계속 틀리다가 이걸 수정하니 맞게 나왔다.

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_G2_3108_로고 {
    static class Rectangle{
        int r1, c1, r2, c2;
        public Rectangle(int r1, int c1, int r2, int c2){
            this.r1 = r1;
            this.r2 = r2;
            this.c1 = c1;
            this.c2 = c2;
        }
    }
    static class Cell{
        boolean[] road = new boolean[4]; //4방향 길
        public void setRoad(int i){
            road[i] = true;
        }
    }
    static class Pos{
        int r, c;
        public Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    static int N;
    static Rectangle[] rects;
    static Cell[][] map;
    static int R = 1001, C = 1001; //-500~500 (+500) -> 0~1000
    static int[] dr = {1, 0, -1, 0};
    static int[] dc = {0, -1, 0, 1}; //상좌하우(0123)
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(in.readLine());
        rects = new Rectangle[N];
        for (int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(in.readLine());
            int r1 = Integer.parseInt(st.nextToken()) + 500;
            int c1 = Integer.parseInt(st.nextToken()) + 500;
            int r2 = Integer.parseInt(st.nextToken()) + 500;
            int c2 = Integer.parseInt(st.nextToken()) + 500;
            rects[i] = new Rectangle(r1, c1, r2, c2);
        }

        //사각형을 맵에 그리기
        map = new Cell[R][C];
        for (int i = 0; i < R; i++){
            for (int j = 0; j < C; j++){
                map[i][j] = new Cell();
            }
        }
        drawRect();

        //첫 번째 사각형부터 dfs
        visited = new boolean[R][C];
        int cnt = 0;
        for (Rectangle rect : rects){
            if (visited[rect.r1][rect.c1]) continue;

            //방문하지 않았다면
            visited[rect.r1][rect.c1] = true;
//            System.out.println(" #### " + rect.r1 + " " + rect.c1);
            bfs(new Pos(rect.r1, rect.c1));
            cnt++;
        }
//        System.out.println(cnt);
        System.out.println(cnt - 1 + ((visited[500][500])? 0 : 1));
    }

    private static void bfs(Pos pos) {
        Queue<Pos> q = new ArrayDeque<>();
        q.offer(pos);

        while(!q.isEmpty()){
            Pos cur = q.poll();
//            System.out.println(cur.r + " " + cur.c);

            for (int di = 0; di < 4; di++){
                if (!map[cur.r][cur.c].road[di]) continue; //연결되어 있지 않음
//                System.out.println("dir: " + di);
                //연결되어 있다면 방문 체크
                int nr = cur.r + dr[di];
                int nc = cur.c + dc[di];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc]) continue;
                visited[nr][nc] = true;
//                System.out.println("push : " + nr + " " + nc);
                q.offer(new Pos(nr, nc));
            }
        }
    }

    private static void drawRect() {
        for (Rectangle rect : rects){
            map[rect.r1][rect.c1].setRoad(0);
            map[rect.r1][rect.c1].setRoad(3);

            map[rect.r1][rect.c2].setRoad(0);
            map[rect.r1][rect.c2].setRoad(1);

            map[rect.r2][rect.c1].setRoad(2);
            map[rect.r2][rect.c1].setRoad(3);

            map[rect.r2][rect.c2].setRoad(1);
            map[rect.r2][rect.c2].setRoad(2);

            //좌우 방향(1, 3) : r을 고정
            for (int c = rect.c1+1; c < rect.c2; c++){
                map[rect.r1][c].setRoad(1);
                map[rect.r1][c].setRoad(3);
                map[rect.r2][c].setRoad(1);
                map[rect.r2][c].setRoad(3);
            }

            //상하 방향(0, 2) : c을 고정
            for (int r = rect.r1+1; r < rect.r2; r++){
                map[r][rect.c1].setRoad(0);
                map[r][rect.c1].setRoad(2);
                map[r][rect.c2].setRoad(0);
                map[r][rect.c2].setRoad(2);
            }
        }
    }
}