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

o 문제

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

 

---

 

 

o 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.*;
import java.util.StringTokenizer;

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] branch;
    static boolean[][] visited;
    static int N, cnt;


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

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

        branch = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {

            String str = br.readLine();
            for (int j = 0; j < branch[i].length; j++) {
                branch[i][j] = str.charAt(j) - '0';
            }
        }


        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < branch[i].length; j++) {
                cnt = 0;
                if (branch[i][j] == 1 && !visited[i][j]) {
                    cnt++;
                    dfs(i, j);
                }
                if (cnt > 0) list.add(cnt);
            }
        }
        Collections.sort(list);
        System.out.println(list.size());
        for (Integer num : list) {
            System.out.println(num);
        }
    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;

        for (int k = 0; k < 4; k++) {

            int nx = x + dx[k];
            int ny = y + dy[k];

            if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[nx][ny] && branch[nx][ny] == 1) {
                cnt++;
                dfs(nx, ny);
            }

        }
    }
}

 

---

 

o 풀이 방식

 

1. 배열을 돌면서 1인 부분을 만나면 방문을 안했으면 dfs를 돌렸다.

그 부분과 겹친 1인 부분의 개수를 세서 cnt를 배열에 저장한다.

List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < branch[i].length; j++) {
                cnt = 0;
                if (branch[i][j] == 1 && !visited[i][j]) {
                    cnt++;
                    dfs(i, j);
                }
                if (cnt > 0) list.add(cnt);
            }
        }

 

 

2. dx, dy를 통해 상하좌우를 확인하며 위에서 1이였던 부분와 붙어 있는 1의 개수를 센다.

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

...

public static void dfs(int x, int y) {
        visited[x][y] = true;

        for (int k = 0; k < 4; k++) {

            int nx = x + dx[k];
            int ny = y + dy[k];

            if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[nx][ny] && branch[nx][ny] == 1) {
                cnt++;
                dfs(nx, ny);
            }

        }
    }

 

상하좌우 체크하는 if 조건문에서 if (!visited[nx][ny] && branch[nx][ny] == 1 && 0 <= nx && nx < N && 0 <= ny && ny < N)

라고 썼다가, 오류가 나서 체크를 해보니 nx, ny의 범위를 먼저 체크한 다음에 visited, branch를 확인해야 한다는 주의점이 있었다!.. 메모 ***

 

3. list를 오름차순으로 정렬하고, list의 개수를 출력 한 다음 list의 요소들을 출력한다!

        Collections.sort(list);
        System.out.println(list.size());
        for (Integer num : list) {
            System.out.println(num);
        }