[코테] 백준 2667 단지 번호붙이기: DFS Java

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

 

이전 것들이랑 비슷하다.

그런데 출력시 '단지의 갯수'와 '단지 별 집 갯수'를 출력해야되서 그 부분만 저장하면 된다.

나는 Map을 사용했다.

 

1) 입력 부분

    static int N;
    static int[][] map;
    static boolean[][] visit;
    static Map<Integer, Integer> houseCount = new HashMap<>();
    static int count = 0; // 단지 수
    static int[] dx = { 0, -1, 0, 1 };
    static int[] dy = { 1, 0, -1, 0 };

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 지도의 크기
        map = new int[N][N];
        visit = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            map[i] = Arrays.stream(st.nextToken().split("")).mapToInt(Integer::parseInt).toArray();
        }

    }

헉 지금 보니... map(지도)와 Map(has map)이 같이 쓰이다보니 매우 혼란스럽다.

다음엔 변수명을 더 주의해야겠다.

 

map[n][n] (지도)를 저장할 때, st.nextToken().split("")을 쓰다보니 String type으로 저장할까 잠깐 고민했다.

stream을 쓰는 게 느려질 것 같아서였다.

그러나 비교 문제가 많고 결국 원시 타입인 int가 더 성능상 이점이 있을 것 같아 stream을 쓰더라도 int 타입을 쓰기로 결정했다.

 

2) dfs 함수 로직

houseNum은 단지별 집 갯수를 저장하기 위한 idx값이다.

    public static void dfs(int i, int j, int houseNum) {
        visit[i][j] = true;
        houseCount.put(houseNum, houseCount.getOrDefault(houseNum, 0) + 1);

        if(!visit[i][j] || map[i][j] == 0) {
            return;
        }

        for (int k = 0; k < 4; k++) {
            int ny = i + dy[k];
            int nx = j + dx[k];

            if(nx >= 0 && ny >= 0 && nx < N && ny < N) {
                if(!visit[ny][nx] && map[ny][nx] == 1) {
                    dfs(ny, nx, houseNum);
                }
            }
        }
    }

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class baekjoon_2667 {
    static int N;

    static int[][] map;
    static boolean[][] visit;
    static Map<Integer, Integer> houseCount = new HashMap<>();
    static int count = 0; // 단지 수
    static int[] dx = { 0, -1, 0, 1 };
    static int[] dy = { 1, 0, -1, 0 };

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 지도의 크기
        map = new int[N][N];
        visit = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            map[i] = Arrays.stream(st.nextToken().split("")).mapToInt(Integer::parseInt).toArray();
        }

        int houseNum = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(!visit[i][j] && map[i][j] == 1) {
                    count++;
                    dfs(i, j, houseNum++);
                }
            }
        }

        System.out.println(count);

        List<Integer> keySet = new ArrayList<>(houseCount.keySet());
        keySet.sort(Comparator.comparing(o -> houseCount.get(o)));

        for(int key: keySet) {
            System.out.println(houseCount.get(key));
        }

    }

    public static void dfs(int i, int j, int houseNum) {
        visit[i][j] = true;
        houseCount.put(houseNum, houseCount.getOrDefault(houseNum, 0) + 1);

        if(!visit[i][j] || map[i][j] == 0) {
            return;
        }

        for (int k = 0; k < 4; k++) {
            int ny = i + dy[k];
            int nx = j + dx[k];

            if(nx >= 0 && ny >= 0 && nx < N && ny < N) {
                if(!visit[ny][nx] && map[ny][nx] == 1) {
                    dfs(ny, nx, houseNum);
                }
            }
        }
    }
}

 

답을 전혀 안보고 혼자 힘으로 푼 첫 dfs 문제다.

뿌듯!! 내일부터는 bfs로 간다.