Baekjoon 문제 풀기 (2667번 : 단지번호붙이기) Java

2667번 : 단지번호붙이기

1. 문제읽기

---

알고리즘 관련 포스팅은 점차 빈도를 줄이려고 하고 있는데, 그 와중 바보같은 실수를 하는 것(..) 들은 기록 겸으로 해서 남겨놓으려고 한다.

2. 제출 코드

---

분명히 로직에는 문제가 없다고 생각했는데 계속 틀린 답이 나왔다.
답을 찾아 비교했지만 내가 봤을 때는 정말 차이가 없었다.
무엇이 문제였을까!!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ2667 {
    static int[][] apart;
    static boolean[][] checked;
    static int[] count;
    static int countNum = 0;
    static int n;


    static int[] dx = {0,0,-1,1};
    static int[] dy = {-1,1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());

        apart = new int[n][n];
        checked = new boolean[n][n];
        count = new int[n*n];

        for(int i = 0; i < n; i++) {
            String s = br.readLine();
            for(int j = 0; j < n; j++) {
                apart[i][j] = s.charAt(j) - '0';
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(apart[i][j] != 0 && !checked[i][j]) {
                    countNum++;
                    bfs(i,j);
                }
            }
        }

        Arrays.sort(count);
        sb.append(countNum).append("\n");

        for(int i : count) {
            if(i != 0) {
                sb.append(i).append("\n");
            }
        }

        System.out.println(sb);

    }

    static void bfs(int x, int y) {
        Queue<Integer[]> q = new LinkedList<>();
        checked[x][y] = true;
        q.offer(new Integer[] {x,y});
        count[countNum]++;

        while(!q.isEmpty()) {
            Integer[] target = q.poll();
            int tX = target[0];
            int tY = target[1];

            for(int i = 0; i < dx.length; i++) {
                tX += dx[i];
                tY += dy[i];

                if(tX >= 0 && tY >= 0 && tX < n && tY < n) {
                    if((apart[tX][tY] != 0) && !checked[tX][tY]) {
                        q.offer(new Integer[] {tX, tY});
                        checked[tX][tY] = true;
                        count[countNum]++;
                    }
                }
            }

        }
    }
}

3. 공부할 것

---

답은 바로 이부분이였다.

while(!q.isEmpty()) {
    Integer[] target = q.poll();
    int tX = target[0];
    int tY = target[1];

    for(int i = 0; i < dx.length; i++) {
        tX += dx[i];
        tY += dy[i];

        if(tX >= 0 && tY >= 0 && tX < n && tY < n) {
            if(apart[tX][tY] == 1 && !checked[tX][tY]) {
                q.offer(new Integer[] {tX, tY});
                checked[tX][tY] = true;
                count[countNum]++;
            }
        }
    }

}

아래와 같이 바꾸어야 한다.
tX와 tY는 for문이 돌때만 사용하고, 어차피 while문 안에서 초기화를 시켜주기 때문에 값을 갱신하기만 하면 문제가 없다고 생각했다.(사실 갱신되는 것도 아님 누적됨)

그러나 for문을 돌 때 사용된 tX와 tY의 값이 초기화가 되지 않기 때문에, 즉, tX가 0 tY가 0이고 dx와 dy값을 더한 갱신된 값이 1, 1이라고 한다면 두번째 for문이 돌 때는 이 1,1에 dx와 dy값이 각각 더해지기 때문에 완전 다른 값이 나오게 된다.

while(!q.isEmpty()) {
    Integer[] target = q.poll();
    int cX = target[0];
    int cY = target[1];

    for(int i = 0; i < dx.length; i++) {
        int tX = cX + dx[i];
        int tY = cY + dy[i];

        if(tX >= 0 && tY >= 0 && tX < n && tY < n) {
            if(apart[tX][tY] == 1 && !checked[tX][tY]) {
                q.offer(new Integer[] {tX, tY});
                checked[tX][tY] = true;
                count[countNum]++;
            }
        }
    }

}

따라서 기존 값 cX와 cY, 더해서 인접 좌표로 이동하는 값 tX, tY를 구분지어주어야 제대로 동작한다.
제대로 로직을 이해하고 생각해서 따라갔다면 나오지 않았을 실수였는데 최근 BFS, DFS 문제만 풀다보니 외워서 풀려고 해서 문제가 생긴 것 같다.
차근차근 생각하며 풀려고 노력해야겠다.
아래는 최종 정답 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ2667 {
    static int[][] apart;
    static boolean[][] checked;
    static int[] count;
    static int countNum = 0;
    static int n;


    static int[] dx = {0,0,-1,1};
    static int[] dy = {-1,1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());

        apart = new int[n][n];
        checked = new boolean[n][n];
        count = new int[n*n];

        for(int i = 0; i < n; i++) {
            String s = br.readLine();
            for(int j = 0; j < n; j++) {
                apart[i][j] = s.charAt(j) - '0';
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(apart[i][j] != 0 && !checked[i][j]) {
                    countNum++;
                    bfs(i,j);
                }
            }
        }

        Arrays.sort(count);
        sb.append(countNum).append("\n");

        for(int i : count) {
            if(i != 0) {
                sb.append(i).append("\n");
            }
        }

        System.out.println(sb);

    }

    static void bfs(int x, int y) {
        Queue<Integer[]> q = new LinkedList<>();
        checked[x][y] = true;
        q.offer(new Integer[] {x,y});
        count[countNum]++;

        while(!q.isEmpty()) {
            Integer[] target = q.poll();
            int cX = target[0];
            int cY = target[1];

            for(int i = 0; i < dx.length; i++) {
                int tX = cX + dx[i];
                int tY = cY + dy[i];

                if(tX >= 0 && tY >= 0 && tX < n && tY < n) {
                    if(apart[tX][tY] == 1 && !checked[tX][tY]) {
                        q.offer(new Integer[] {tX, tY});
                        checked[tX][tY] = true;
                        count[countNum]++;
                    }
                }
            }

        }
    }
}