백준 2667번 단지번호붙이기 자바 풀이 및 정답

백준 2667번 단지번호붙이기 문제 설명

대표적인 DFS 방식 탐색으로 볼 수 있으며 표 형태에서 DFS로 탐색해나가는 방법으로 풀어나갈 수 있을 것 같습니다.

 

 

012

백준 2667번 단지번호붙이기 그림 설명

그림1 - 작은 테스트 케이스로 위와 같다고 구성해봅니다. 행은 i, 열은 j로 돌게됩니다.

그림2 - 4방향을 각각 탐색하면서 더 나아갈 곳이 있다면 그만큼 전진시켜줍니다. dx, dy와 같이 배열형태로 나아가는 방향을 표기할 수 있습니다. 기존 i, j에 대해 dx, dy를 각각 더해주면 표에서 다음위치로 전진하는 개념입니다 DFS를 끝마치면 하나의 단지를 찾은 개념이 됩니다. for문을 다 돌고나면 그림 3과 같은 형태로 총 3개의 단지를 찾게됩니다.

 

 

백준 2667번 단지번호붙이기 정답 코드(자바)

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

public class Main {
    static boolean[][] visitedArray;
    static int count;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader brd = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(brd.readLine());

        int[][] board = new int[n][n];
        visitedArray = new boolean[n][n];
        for (int i=0; i<n; i++) {
            String line = brd.readLine();
            int j = 0;
            for (char a : line.toCharArray()) {
                board[i][j] = a - '0';
                j++;
            }
        }

        ArrayList<Integer> answerArray = new ArrayList<>();
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (visitedArray[i][j]) continue;
                if (board[i][j] == 0) continue;
                count = 0;
                DFS(board, i, j);
                answerArray.add(count);
            }
        }

        StringBuilder sb = new StringBuilder();
        Collections.sort(answerArray);
        sb.append(answerArray.size());
        sb.append("\n");
        for (int x : answerArray) {
            sb.append(x);
            sb.append("\n");
        }
        System.out.println(sb);
    }

    static void DFS(int[][] map, int x, int y) {
        visitedArray[x][y] = true;
        count++;

        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= map.length || ny < 0 || ny >= map.length) continue;
            if (map[nx][ny] == 0 || visitedArray[nx][ny]) continue;
            DFS(map, nx, ny);
        }
    }
}