백준 자바 :: 단지번호붙이기(DFS) / 유기농배추(DFS) / 섬의개수(DFS)

 

단지번호붙이기

 

 

 

 

 

 

import java.util.*;

import java.io.*;

public class Main{

    static int N;

    static int[][] array;

    static boolean[][] visited;

    static int count;

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

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

    static List<Integer> result;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        array = new int[N][N];

        visited = new boolean[N][N];

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

            String line = br.readLine();

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

                array[i][j] = line.charAt(j) - '0';

            }

        }

        result = new ArrayList<Integer>();

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

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

                if(!visited[i][j] && array[i][j] == 1){

                    count = 0;

                    DFS(i,j);

                    result.add(count);

                }

            }

        }

        Collections.sort(result);

        System.out.println(result.size());

        for(int a : result){

            System.out.println(a);

        }

       

    }

    static void DFS(int x, int y){

        count++;

        visited[x][y] = true;

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

            int now_x = x + dx[i];

            int now_y = y + dy[i];

            if(now_x >=0 && now_y >=0 && now_x < N && now_y < N && !visited[now_x][now_y] && array[now_x][now_y] == 1){

                DFS(now_x, now_y);

            }

        }

    }

}

 

 

 

 

 

 

 

유기농배추

 

 

import java.util.*;

import java.io.*;

public class Main{

    static int testcase;

    static int width;

    static int height;

    static int[][] array;

    static boolean[][] visited;

    static int count;

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

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        testcase = Integer.parseInt(st.nextToken());

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

            st = new StringTokenizer(br.readLine());

            width = Integer.parseInt(st.nextToken());

            height = Integer.parseInt(st.nextToken());

            int baechuNum = Integer.parseInt(st.nextToken());

   

            array = new int[width][height];

            visited = new boolean[width][height];

   

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

                st = new StringTokenizer(br.readLine());

                int x = Integer.parseInt(st.nextToken());

                int y = Integer.parseInt(st.nextToken());

   

                array[x][y] = 1;

            }

            count = 0;

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

                for(int j = 0; j < height; j++){

                    if(!visited[i][j] && array[i][j] == 1){

                        count++;

                        DFS(i,j);

                    }

                }

            }

            System.out.println(count);

        }

    }

    static void DFS(int x, int y){

        visited[x][y] = true;

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

            int now_x = x + dx[i];

            int now_y = y + dy[i];

            if(now_x >=0 && now_y >=0 && now_x < width && now_y < height && !visited[now_x][now_y] && array[now_x][now_y] == 1){

                DFS(now_x, now_y);

            }

        }

    }

}

 

 

 

 

 

섬의개수

 

 

 

import java.util.*;

import java.io.*;

public class Main{

    static int width;

    static int height;

    static int[][] array;

    static boolean[][] visited;

    static int count;

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

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

       

        while(true){

            StringTokenizer st = new StringTokenizer(br.readLine());

            width = Integer.parseInt(st.nextToken());

            height = Integer.parseInt(st.nextToken());

            if(width == 0 && height == 0) break;

            array = new int[height][width]; // 초기화시 행열 주의!!

            visited = new boolean[height][width];

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

                st = new StringTokenizer(br.readLine());

                for(int j = 0; j < width; j++){

                    array[i][j] = Integer.parseInt(st.nextToken());

                }

            }

            count = 0;

            for(int i = 0; i < height; i++){ // 높이랑 너비 주의!!!

                for(int j = 0; j < width; j++){

                    if(!visited[i][j] && array[i][j] == 1){

                        count++;

                        DFS(i, j);

                    }

                }

            }

            System.out.println(count);

        }

    }

    static void DFS(int x, int y){

        visited[x][y] = true;

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

            int now_x = x + dx[i];

            int now_y = y + dy[i];

            // 여기서도 가로 세로 주의!!!

            if(now_x >=0 && now_y >=0 && now_x < height && now_y < width && !visited[now_x][now_y] && array[now_x][now_y] == 1){

                DFS(now_x, now_y);

            }

        }

    }

}