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

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

 

 

문제 파악

-네트워크 문제와 비슷하게, 연결 된 집을 갯수를 모두 카운트하고

-한 단지가 끝나면 다른 단지도 순회한다.

-N X N 크기

 

접근 방법

-DFS로 탐색(재귀 탐색)

-탐색 후 visited 체크(혹은 0으로 변경?)

-재귀 호출 일어날 때마다 cnt증가, 종료될 때마다 cnt합산

-다른 집 옮겨갈 때 dfs 사용한다. (dfs 한번 당 1)

-결과값은 재귀호출 내에서 관리하는 것이 아니라

매 dfs마다 새로운 변수를 만들어 타고타고 누적하며 

그 값을 리턴하면 1씩 누적되는 형태(모아서 바치는 형태로 생각하자.)

-DFS함수는 int형태를 리턴하고, 한 단지의 순회가 끝나면 모아모아 받은 결과값을 메인함수에서 저장

 

코드 구현

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] graph = new int[n][n];
        for(int i = 0; i < n; i++) {
            String s = br.readLine();
            for(int j = 0; j < n; j++) {
                graph[i][j] = s.charAt(j) - '0';
            }
        }
        List<Integer> answer = new ArrayList<Integer>();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(graph[i][j] == 1 && isValid(graph,i,j)) {
                    int result = dfs(graph,i,j);//첫 시작
                    answer.add(result);//단지 별 아파트 갯수 누적
                }
            }
        }
        System.out.println(answer.size());
        Collections.sort(answer);
        for(int i = 0; i < answer.size(); i++) {
            System.out.println(answer.get(i));
        }
    }

    public static int dfs(int[][] graph,int x,int y) {
        int cnt=1;
        graph[x][y] = 0;

        int[] toX = {-1, 1, 0, 0};
        int[] toY = {0, 0, -1, 1};
        for (int i = 0; i < 4; i++) {
            int ax = x + toX[i];
            int ay = y + toY[i];
            if (isValid(graph, ax, ay)) {
                cnt += dfs(graph, ax, ay);
            }
        }
        return cnt;
    }

    public static boolean isValid(int[][] graph,int x,int y){
        if(x<0 || x>=graph.length || y<0 || y>=graph[0].length || graph[x][y]!=1){
            return false;
        }
        return true;
    }
}

 

배우게 된 점

-DFS 에서 카운트를 해야한다면(단지 카운트가 아니라, 집 수 카운트) -> 리턴값을 주는 것도 생각해보자.

-리턴하며 1씩 누적하여 한 단지 당 총 집 수를 카운트할 수 있는 것.

-s.charAt(i) -'0' => char 형태를 int형태로 저장하는 방법