[백준2667:단지번호붙이기][JAVA]

예전에 python으로 한 번 푼 적이 있는 문제!

😩 문제 접근과 틀린 이유

문제 자체를 어떻게 접근할 지 시간을 많이 사용해서 어떻게 풀 지는 설계를 괜찮게 한 것 같다.
그래서 코드를 다 만들고 돌렸더니 이게 왠 걸..값이 이상하게 나오고 탐색도 제대로 안되었다.
출력까지 하면서 값을 찾았는데 원하는 값이 안 나오고 웬 이상한 값이 자꾸 나와서 아래 틀린 코드에서 30분 이상을 헤매었다.

대충 틀은 다 맞았는데..4방향 이동에서 엄청 큰 실수를 했다.
4방향을 이동하는 것도 기준점은 절대 이동하지 않고 기준점 기준으로 x,y를 더해서 상하좌우를 체크하는건데 기준점을 내가 이동시켜 버리니 당연히 될 리가 없었다.
기준점을 변경하고 나니 예제 입력에서 원하는 값은 잘 나왔고 제출을 했더니...

또 틀렸다. 도데체 이유가 무엇인고..문제를 다시 읽으니

오!름차!순. 으로 출력!

문제를 제대로 읽자..

😥틀린 코드

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

public class Main {
    static List<Integer> Danji = new ArrayList<>();
    static List<List<Integer>> queue = new ArrayList<>();
    //bfs를 통해서 싸악 한 번 검출한다 쳐 근데 다음 거에서 구분 어떻게?
    //=> 판때기 자체에 값을 설정(똑같은 크기에 배열에 처리했는지?
    //=> visited를 사용하는데 사용하기 좀 애매하긴하다..
    static int[][] visited;
    static int[][] graph;

    static int N;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        graph = new int[N][N];
        visited = new int[N][N];

        for(int i = 0; i < N; i++){
            String value = br.readLine();

            for(int j=0; j < N; j++) {
                graph[i][j] = Character.getNumericValue(value.charAt(j));
            }
        }

        for(int i = 0 ; i < N; i++){
            for(int j = 0 ; j < N; j++){
                //값이 1이면서 아직 방문하지 않은 값을 보내자!
                if(graph[i][j] == 1 && visited[i][j] == 0)
                    Danji.add(bfs(i,j));
            }
        }

        System.out.println(Danji.size());
        for(int i = 0 ; i < Danji.size(); i++){
            System.out.println(Danji.get(i));
        }
    }

    static int[] moveX = {0,0,1,-1};
    static int[] moveY = {1,-1,0,0};
    private static int bfs(int i, int j) {
        visited[i][j] = 1;
        int danji = 1;
        //큐에 [i,j] 넣고
        List<Integer> tempIdx = new ArrayList<>();
        tempIdx.add(i);
        tempIdx.add(j);
        queue.add(tempIdx);

        //큐가 비어있지 않다면?
        while(!queue.isEmpty()){
            //remove해서 값 꺼내기
            tempIdx = queue.remove(0);
            int a = tempIdx.get(0);
            int b = tempIdx.get(1);

            //상하좌우 이동해서
            for(int k = 0; k < 4; k++){
                a += moveX[k];
                b += moveY[k];

                if(a == N) a-=1;
                else if(a == -1) a+= 1;

                if(b == N) b-=1;
                else if(b == -1) b+= 1;

                if(graph[a][b] == 1 && visited[a][b] == 0){
                    System.out.println(i + " " + j + " | " +  " " + a + " " + b);
                    tempIdx = new ArrayList<>();
                    tempIdx.add(a);
                    tempIdx.add(b);
                    queue.add(tempIdx);

                    visited[a][b] = 1;
                    danji++;
                }
            }
        }
        return danji;
    }
}

😎 정답코드

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

public class Main {
    static List<Integer> Danji = new ArrayList<>();
    static List<List<Integer>> queue = new ArrayList<>();
    static int[][] visited;
    static int[][] graph;
    static int N;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        graph = new int[N][N];
        visited = new int[N][N];

        for(int i = 0; i < N; i++){
            String value = br.readLine();

            for(int j=0; j < N; j++) {
                graph[i][j] = Character.getNumericValue(value.charAt(j));
            }
        }

        for(int i = 0 ; i < N; i++){
            for(int j = 0 ; j < N; j++){
                //값이 1이면서 아직 방문하지 않은 값을 보내자!
                if(graph[i][j] == 1 && visited[i][j] == 0)
                    Danji.add(bfs(i,j));
            }
        }

        System.out.println(Danji.size());
        Collections.sort(Danji);
        for(int i = 0 ; i < Danji.size(); i++){
            System.out.println(Danji.get(i));
        }
    }

    static int[] moveX = {0,0,1,-1};
    static int[] moveY = {1,-1,0,0};
    private static int bfs(int i, int j) {
        visited[i][j] = 1;
        int danji = 1;
        //큐에 [i,j] 넣고
        List<Integer> tempIdx = new ArrayList<>();
        tempIdx.add(i);
        tempIdx.add(j);
        queue.add(tempIdx);

        //큐가 비어있지 않다면?
        while(!queue.isEmpty()){
            //remove해서 값 꺼내기
            tempIdx = queue.remove(0);
            int a = tempIdx.get(0);
            int b = tempIdx.get(1);

            //상하좌우 이동해서
            for(int k = 0; k < 4; k++){
                int newA = a + moveX[k];
                int newB = b + moveY[k];

                if (newA >= N) newA = N - 1;
                else if (newA < 0) newA = 0;

                if (newB >= N) newB = N - 1;
                else if (newB < 0) newB = 0;

                if(graph[newA][newB] == 1 && visited[newA][newB] == 0){
                    //System.out.println(i + " " + j + " | " +  " " + a + " " + b);
                    tempIdx = new ArrayList<>();
                    tempIdx.add(newA);
                    tempIdx.add(newB);
                    queue.add(tempIdx);

                    visited[newA][newB] = 1;
                    danji++;
                }
            }
        }
        return danji;
    }
}