(7) [C++, Java] 백준 No.2667 : 단지번호붙이기

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/400

# C++(DFS사용)

#include<cstdio>
#include<algorithm>
using namespace std;

int place[26][26];        // 집의 여부 표시
int check[26][26] = {};   // 0 : 방문하지 않은 것, 1이상 : 방문하였고, 부지번호
int ans[25*25] = {};      // 부지별 개수 저장
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int n;

void dfs(int i, int j, int cnt)
{
    check[i][j] = cnt;

    for(int k = 0; k < 4; k++){
        int x = i+dx[k];
        int y = j+dy[k];

        // x: 1~7, y: 1~7 범위안에 있을 때만 탐색 진행
        if(x >= 1 && x <= n && y >= 1 && y <= n){
            if(place[x][y] == 1 && check[x][y] == 0)
                dfs(x, y, cnt);
        }   
    }
}

int main()
{
    // 정보 입력받기
    scanf("%d", &n);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            scanf("%1d", &place[i][j]);
        }
    }

    // 모든 점을 시작점으로 하며 탐색을 진행하고, 연결된 부지에 번호를 표시함
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(place[i][j] == 1 && check[i][j] == 0){
                dfs(i, j, ++cnt);
            }
        }
    }

    // 모든 자리를 돌며 번호의 개수를 셈
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if (place[i][j] == 1){
                ans[check[i][j]] += 1;
            }
        }
    }
    
    // 오름차순으로 정렬
    sort(ans+1, ans+cnt+1);

    // 정답 출력
    printf("%d\n", cnt);
    for(int i = 1; i <= cnt; i++)
        printf("%d\n", ans[i]);
}

# C++(BFS사용)

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

int place[26][26];        // 집의 여부 표시
int check[26][26] = {};   // 0 : 방문하지 않은 것, 1이상 : 방문하였고, 부지번호
int ans[25*25] = {};      // 부지별 개수 저장
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int n;

void bfs(int i, int j, int cnt)
{
    queue<pair<int, int>> q;

    q.push(make_pair(i, j));
    check[i][j] = cnt;

    while(!q.empty())
    {
        pair<int, int> p = q.front();
        q.pop();
        
        for(int k = 0; k < 4; k++){
            int x = p.first + dx[k];
            int y = p.second + dy[k];

            if(x >= 1 && x <= n && y >= 1 && y <= n)
            {
                if (place[x][y] == 1 && check[x][y] == 0){
                    q.push(make_pair(x, y));
                    check[x][y] = cnt;
                }
            }
        }
    }
}

int main()
{
    // 정보 입력받기
    scanf("%d", &n);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            scanf("%1d", &place[i][j]);
        }
    }

    // 모든 점을 시작점으로 하며 탐색을 진행하고, 연결된 부지에 번호를 표시함
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(place[i][j] == 1 && check[i][j] == 0){
                bfs(i, j, ++cnt);
            }
        }
    }

    // 모든 자리를 돌며 번호의 개수를 셈
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if (place[i][j] == 1){
                ans[check[i][j]] += 1;
            }
        }
    }
    
    // 오름차순으로 정렬
    sort(ans+1, ans+cnt+1);

    // 정답 출력
    printf("%d\n", cnt);
    for(int i = 1; i <= cnt; i++)
        printf("%d\n", ans[i]);
}

# Java(DFS사용)

import java.util.*;

class Pair {
    int x;
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static final int[] dx = {0, 0, 1, -1};
    public static final int[] dy = {1, -1, 0, 0};
    public static void dfs(int[][] a, int[][] group, int x, int y, int cnt, int n) {
        group[x][y] = cnt;
        for (int k=0; k<4; k++) {
            int nx = x+dx[k];
            int ny = y+dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                if (a[nx][ny] == 1 && group[nx][ny] == 0) {
                    dfs(a, group, nx, ny, cnt, n);
                }
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        int[][] a = new int[n][n];
        for (int i=0; i<n; i++) {
            String s = sc.nextLine();
            for (int j=0; j<n; j++) {
                a[i][j] = s.charAt(j) - '0';
            }
        }
        int cnt = 0;
        int[][] group = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] == 1 && group[i][j] == 0) {
                    dfs(a, group, i, j, ++cnt, n);
                }
            }
        }
        int[] ans = new int[cnt];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (group[i][j] != 0) {
                    ans[group[i][j]-1]+=1;
                }
            }
        }
        Arrays.sort(ans);
        System.out.println(cnt);
        for (int i=0; i<cnt; i++) {
            System.out.println(ans[i]);
        }
    }
}

# Java(BFS사용)

import java.util.*;

class Pair {
    int x;
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static final int[] dx = {0, 0, 1, -1};
    public static final int[] dy = {1, -1, 0, 0};
    public static void bfs(int[][] a, int[][] group, int x, int y, int cnt, int n) {
        Queue<Pair> q = new LinkedList<Pair>();
        q.add(new Pair(x, y));
        group[x][y] = cnt;
        while (!q.isEmpty()) {
            Pair p = q.remove();
            x = p.x;
            y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if (a[nx][ny] == 1 && group[nx][ny] == 0) {
                        q.add(new Pair(nx, ny));
                        group[nx][ny] = cnt;
                    }
                }
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        int[][] a = new int[n][n];
        for (int i=0; i<n; i++) {
            String s = sc.nextLine();
            for (int j=0; j<n; j++) {
                a[i][j] = s.charAt(j) - '0';
            }
        }
        int cnt = 0;
        int[][] group = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] == 1 && group[i][j] == 0) {
                    bfs(a, group, i, j, ++cnt, n);
                }
            }
        }
        int[] ans = new int[cnt];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (group[i][j] != 0) {
                    ans[group[i][j]-1]+=1;
                }
            }
        }
        Arrays.sort(ans);
        System.out.println(cnt);
        for (int i=0; i<cnt; i++) {
            System.out.println(ans[i]);
        }
    }
}