[BOJ][2667] 단지번호붙이기

1. 문제 링크

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

2. 사용 알고리즘

DFS

3. 풀이

1) 집의 존재여부를 저장하기 위한 배열 arr, 단지의 번호를 붙이기 위한 배열 check 선언

2) (1, 1)부터 반복문을 돌며, 집이 있으면서 단지번호가 0(아직 방문하지 않은 정점)인 정점부터 DFS 탐색 시작

• 현재 정점의 왼쪽 좌표가 유효하고, 집이 존재하고, 단지번호가 0인 경우 → DFS 탐색 계속 진행

• 현재 정점의 위쪽 좌표가 유효하고, 집이 존재하고, 단지번호가 0인 경우 → DFS 탐색 계속 진행

• 현재 정점의 오른쪽 좌표가 유효하고, 집이 존재하고, 단지번호가 0인 경우 → DFS 탐색 계속 진행

• 현재 정점의 아래쪽 좌표가 유효하고, 집이 존재하고, 단지번호가 0인 경우 → DFS 탐색 계속 진행

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/2667.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[33][33];
int check[33][33];
vector<int> v;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int n;

int dfs(int x, int y, int cnt) {
    int ret = 1;
    check[x][y] = cnt;
    for(int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && arr[nx][ny] && !check[nx][ny]) {
            ret += dfs(nx, ny, cnt);
        }
    }
    return ret;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        string temp; cin >> temp;
        for(int j = 1; j <= n; ++j) arr[i][j] = temp.at(j - 1) - 48;
    }
    int cnt = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(arr[i][j] && !check[i][j]) v.push_back(dfs(i, j, ++cnt));
        }
    }
    sort(v.begin(), v.end());
    cout << cnt << "\n";
    int len = v.size();
    for(int i = 0; i < len; ++i) cout << v[i] << "\n";
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/2667.java

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 n;
    static int arr[][] = new int[33][33];
    static int check[][] = new int[33][33];
    static ArrayList<Integer> v = new ArrayList<>();
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, -1, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        for(int i = 1; i <= n; ++i) {
            String temp = br.readLine();
            for(int j = 1; j <= n; ++j) arr[i][j] = temp.charAt(j - 1) - 48;
        }
        int cnt = 0;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(arr[i][j] == 1 && check[i][j] == 0) v.add(dfs(i, j, ++cnt));
            }
        }
        Collections.sort(v);
        sb.append(cnt).append("\n");
        int len = v.size();
        for(int i = 0; i < len; ++i) sb.append(v.get(i)).append("\n");
        System.out.println(sb);
    }

    public static int dfs(int x, int y, int cnt) {
        int ret = 1;
        check[x][y] = cnt;
        for(int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && arr[nx][ny] == 1 && check[nx][ny] == 0) {
                ret += dfs(nx, ny, cnt);
            }
        }
        return ret;
    }
}