[Algorithm] 백준 2667, 1012 DFS 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 백준 2667, 1012번의 자바 풀이를 작성하고자 합니다.

두 문제 모두 입력 처리만 다르게 하되 동일한 dfs로 해결하는 문제이므로 함께 정리하도록 하겠습니다.!

 

문제 링크: https://www.acmicpc.net/problem/2667

문제 링크: https://www.acmicpc.net/problem/1012

 

1. 코드 

 

<Boj2667>

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

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

public class Boj2667 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        Villa villa = new Villa(n);
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            villa.init(i, str); // villa 초기화
        }
        
        List<Integer> villas = villa.calculateTotalVilla();
        Collections.sort(villas); // villa 정렬

        System.out.println(villas.size()); // 다른 단지 수 출력
        
        StringBuilder sb = new StringBuilder();
        for (Integer v : villas) {
            sb.append(v).append('\n');
        }
        
        System.out.println(sb); // 단지의 하우스 출력
    }    
}

class Villa {
    
    class House {
        int num; // 하우스 1 or 0
        boolean visited; // 방문 여부
        
        house(int num) {
            this.num = num;
        }
    }
    
    static int count; // static으로 단지 개수 출력
    static final int[] D_X = {-1, 0, 1, 0}; // 왼 - 오 좌표
    static final int[] D_Y = {0, 1, 0, -1}; // 상 - 아 좌표
    
    House[][] houses; // 하우스 이차원 배열
    List<Integer> counts = new ArrayList<>(); // count를 담을 list
    
    Villa(int n) {
        houses = new House[n][n];
    } // 생성자
    
    void init(int idx, String str) {
        for (int i = 0; i < houses.length; i++) {
            houses[idx][i] = new house(Character.getNumericValue(str.charAt(i))); // 초기화
        }
    }
    
    List<Integer> calculateTotalVilla() { // 총 빌라 수 구하기
        for (int i = 0; i < houses.length; i++) {
            for (int j = 0; j < houses[0].length; j++) {

                // 한번도 방문하지 않으면서 num이 1인 하우스 dfs
                if (!houses[i][j].visited && houses[i][j].num == 1) {
                    count = 0;
                    dfs(i, j);
                    counts.add(count);
                }
            }
        }
        return counts;
    }

    private void dfs(int x, int y) {
        if ((!houses[x][y].visited) && (houses[x][y].num == 1)) {
            houses[x][y].visited = true; // 방문한 곳 true 처리
            ++count;
            for (int k = 0; k < 4; k++) {
                int newX = D_X[k] + x; // 앞 서 정의한 x 좌표
                int newY = D_Y[k] + y; // 앞 서 정의한 y 좌표
                if (validRange(newX, newY)) dfs(newX, newY); // dfs 재귀
            }
        }
     }

     // house의 배열에 유효한 인덱스인지 판단
    private boolean validRange(int x, int y) {
        return (x >= 0) && (y >= 0) && (x < houses.length) && (y < houses.length);
    }
}

 

 

<Boj1012>

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

import java.util.List;
import java.util.ArrayList;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

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

        int t = parseInt(br.readLine());
        int[] result = new int[t];
        int m, n, k;

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            m = getInt(st);
            n = getInt(st);
            k = getInt(st);
            Field field = new Field(m, n);

            for (int j = 0; j < k; j++) {
                st = new StringTokenizer(br.readLine());
                field.cabbages[getInt(st)][getInt(st)] = field.setCabbage();
            }
            field.calculateWhiteBug(m, n);
            result[i] = field.counts.size();
        }

        for (int r : result) {
            System.out.println(r);
        }
    }

    static int getInt(StringTokenizer st) {
        return parseInt(st.nextToken());
    }
}

class Field {

    static final int[] D_X = {1, 0, -1, 0};
    static final int[] D_Y = {0, 1, 0, -1};

    Cabbage[][] cabbages;
    List<Integer> counts = new ArrayList<>();

    class Cabbage {
        int num;
        boolean visited;

        Cabbage(int num) {
            this.num = num;
        }
    }

    Field(int m, int n) {
        cabbages = new Cabbage[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cabbages[i][j] = new Cabbage(0);
            }
        }
    }

    Cabbage setCabbage() {
        return new Cabbage(1);
    }


    void calculateWhiteBug(int m, int n) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (validRange(i, j) && !cabbages[i][j].visited && cabbages[i][j].num == 1) {
                    dfs(i, j);
                    counts.add(1);
                }
            }
        }
    }

    void dfs(int x, int y) {
        if (!cabbages[x][y].visited && cabbages[x][y].num == 1) {
            cabbages[x][y].visited = true;
            for (int i = 0; i < 4; i++) {
                int newX = D_X[i] + x;
                int newY = D_Y[i] + y;
                if (validRange(newX, newY)) dfs(newX, newY);
            }
        }
    }

    boolean validRange(int x, int y) {
        return x >= 0 && y >= 0 && x < cabbages.length && y < cabbages[0].length;
    }
}

 

2. 중요한 포인트

 

-  dfs를 적용하기 위해, 방문 가능한 하우스(노드)가 무엇인지 판단하기 위해 visited라는 boolean을 설정해야 합니다.

-  dfs 메서드가 재귀로 호출되므로 newX, newY라는 새로운 좌표로 dfs에 인자로 넣어주어야 합니다. 

-  ArrayIndexOutOfBoundsException이 발생할 수 있으므로 새롭게 생성되는 newX, newY가 x >= 0, y >= 0 그리고
house.length의 길이보다 작아야 houses[][] 배열에 인덱스로 접근할 수 있습니다.

 

 

 

3. 재귀적 원리로 dfs() 활용하기

 

void dfs(int idx) {
    Node root = nodes[idx]; // root node 가져오기
    root.visitedDfs = true; // 방문 처리
    listDfs.add(root.u); // 방문한 것 출력을 위해 배열에 추가
    for (Node n : root.adjacent) {
        if (!n.visitedDfs) {
            n.visitedDfs = true;
            dfs(n.u);
        }
    }
}

 

일반적으로 dfs를 구현하는데 사용되는 샘플 코드는 다음과 같습니다.

nodes[idx]에서 root 노드를 가져온 후, node에 인접한 adjacent 노드들을 가져온 후, 방문 여부를 판단하고 방문하지 않았다면 
방문 여부를 등록한 후 dfs()로 메서드를 다시 호출합니다.

 

이와같은 원리로 이 문제에서도 방문 여부 false를  판단하고 문제에서 추가로 제시한 1인 번호인지를 체크하고
방문 여부를 true로 설정합니다. 이 후 인접한 노드 (여기서는 인접 좌표)를 설정한 후 인접한 노드로 다시 dfs를 적용합니다.

 

private void dfs(int x, int y) {
    if ((!houses[x][y].visited) && (houses[x][y].num == 1)) {
        houses[x][y].visited = true; // 방문한 곳 true 처리
        ++count;
        for (int k = 0; k < 4; k++) {
            int newX = D_X[k] + x; // 앞 서 정의한 x 좌표
            int newY = D_Y[k] + y; // 앞 서 정의한 y 좌표
            if (validRange(newX, newY)) dfs(newX, newY); // dfs 재귀
        }
    }
 }

 

 

이상입니다! 감사합니다 ~!