Baekjoon[2667] - 단지번호붙이기

링크

Baekjoon[2667]

문제설명

• BFS OR DFS

문제풀이

• BFS OR DFS

문제코드_BFS

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main2667 {
    public static int[][] dir= {
            {-1,0},    
            {1,0},    
            {0,-1},    
            {0,1}    
    };
    public static void main(String[] args) throws NumberFormatException, IOException {
        int ans=0;
        System.setIn(new FileInputStream("res/baekjoon/2667.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[][] map = new int[N][N];
//        visit를 boolean으로 하면 단지수 출력할거 또필요
//        visit를 int로 하면 단지또한 구분 가능하다.
//        ++하면 map[][] 하나로 구분가능

        boolean[][] visit = new boolean[N][N];
        String line;
        for (int i = 0; i < N; i++) {
            line = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = line.charAt(j)-'0';

            }
        }

        LinkedList<int[]> q = new LinkedList<>();
        int count=2;
        int[] now;
        int nr=0;
        int nc=0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(map[i][j]!=0 && map[i][j]==1) {    //벽이 아니며, visit 가능한 경우
                    q.add(new int[]{i,j});
                    map[i][j]=count;
                    while(!q.isEmpty()) {
                        now = q.poll();
                        for (int d = 0; d < 4; d++) {
                            nr = now[0]+dir[d][0];
                            nc = now[1]+dir[d][1];
//                            경계 안에서 벽이 아니며, visit 가능한 경우 다음 조사 node 추가
                            if(nr>=0 && nr<N && nc>=0 && nc<N && map[nr][nc]!=0 && map[nr][nc]==1) {
                                q.add(new int[]{nr,nc});
                                map[nr][nc]=count;
                            }
                        }
                    }
                    //한 동이 만들어 졌음.
                    count++;
                }
            }
        }

        ans = count-2;
        int[] g_count = new int[count];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                g_count[map[i][j]]++;
            }
        }

        int[] ans_count = Arrays.copyOfRange(g_count, 2, count);
        Arrays.sort(ans_count);
        System.out.println(ans);
        for (int cnt: ans_count) {
            System.out.println(cnt);
        }
    }
}

문제코드_DFS

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main2667_DFS {
    public static int[][] dir= {
            {-1,0},    
            {1,0},    
            {0,-1},    
            {0,1}    
    };
    public static int count=2;
    public static int[][] map;
    public static int N;
    public static void DFS(int[] xy) {
        map[xy[0]][xy[1]]=count;    //visit
        int nr=0;
        int nc=0;
        for (int d = 0; d < 4; d++) {
            nr= xy[0]+dir[d][0];
            nc= xy[1]+dir[d][1];
//            경계 안에서, 탐색할 칸이 벽이아니고, 1(탐색가능한 경우)
            if(nr>=0 && nr<N && nc>=0 && nc<N && map[nr][nc]!=0 && map[nr][nc]==1) {
                DFS(new int[] {nr,nc});
            }
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        int ans=0;
        System.setIn(new FileInputStream("res/baekjoon/2667.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
//        visit를 boolean으로 하면 단지수 출력할거 또필요
//        visit를 int로 하면 단지또한 구분 가능하다.
//        ++하면

        String line;
        for (int i = 0; i < N; i++) {
            line = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = line.charAt(j)-'0';

            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(map[i][j]==1) {
                    DFS(new int[] {i,j});
                    count++;
                }
            }
        }


        ans = count-2;
        int[] g_count = new int[count];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                g_count[map[i][j]]++;
            }
        }

        int[] ans_count = Arrays.copyOfRange(g_count, 2, count);
        Arrays.sort(ans_count);
        System.out.println(ans);
        for (int cnt: ans_count) {
            System.out.println(cnt);
        }
    }
}

아쉬운점

• 경계탐색 조건문에서 최대크기를 상수로 둬서 에러났었음.

잘한점

• 공간을 효율적을 사용
  • visit를 boolean으로 하면 단지수 출력할거 또필요
  • visit를 int로 하면 단지또한 구분 가능하다.
  • map++하면 map[][] 하나로 구분가능
• BFS 사용
• DFS 사용