백준

2667번: 단지번호붙이기

bingual 2022. 2. 24. 22:40
반응형

 

 

 

 

풀이

 

여러가지 방법으로 풀 수 있지만 dfs 카테고리에 있는 문제라 dfs를 이용해서 풀었습니다.

 

graph[0][0] ~ graph[n-1][n-1] 까지 돌면서 방문하지 않은 곳에서 dfs를 호출합니다.

dfs 함수 안에서 재귀로 dfs가 재호출 될 때마다 연결된 단지로 전진한 것이므로 count를 1씩 증가해줍니다.

처음에 호출한 dfs가 끝나면 count를 num안에 넣고 마지막에 출력할 수 있도록 저장하고, 단지 그룹 1개를 다 탐색한 것이므로 result를 1 증가시킨뒤 count를 0으로 초기화 합니다.

 

 

 

 

 

 

 

자바풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

    static int count = 0;
    private static int n;
    private static int[][] graph = new int[25][25];

    private static boolean dfs(int x, int y) {
        if (x <= -1 || x >=n || y <= -1 || y >= n) {
            return false;
        }
        if (graph[x][y] == 1) {
            graph[x][y] = 0;
            count += 1;

            dfs(x - 1, y);
            dfs(x, y - 1);
            dfs(x + 1, y);
            dfs(x, y + 1);
            return true;
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        ArrayList<Integer> num = new ArrayList<>();

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

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < n; j++) {
                graph[i][j] = str.charAt(j) - '0';
            }
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(i, j)) {
                    num.add(count);
                    result += 1;
                    count = 0;
                }
            }
        }

        Collections.sort(num);

        System.out.println(result);
        for (int i : num) {
            sb.append(i).append("\n");
        }
        System.out.print(sb);
    }
}

 

 

 

 

 

 

 

파이썬

from sys import stdin

def dfs(x, y):
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
   
    if graph[x][y] == 1:
        graph[x][y] = 0
        global count
        count += 1
       
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
               
        return True
    return False

n = int(input())

num = []
graph = [list(map(int, stdin.readline().rstrip())) for _ in range(n)]

count = 0
result = 0

for i in range(n):
    for j in range(n):
        if dfs(i, j) == True:          
            num.append(count) 
            result += 1
            count = 0        
num.sort()
print(result)
for i in num:
    print(i)