2583 : 영역 구하기 - 연결 컴포넌트, DFS

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

2583번: 영역 구하기

문제요약

connected component 개수와 넓이 구하기

 

난이도

Silver 1

---

풀이 포인트

• DFS
• 일반적 x,y좌표와 2차원 배열 인덱스 간의 매핑

---

REVIEW

dfs 문제 드디어 한 번에 정답.. 감격적

이 문제는 배열 표기와 좌표 표기가 헷갈려 for문 범위 지정이 어려웠다.

일반 좌표를 x축 회전, 그리고 y좌표와 x좌표를 바꾼 것이 2차원 배열의 인덱스와 매핑된다.

쓰면서도 무슨 말인지 모르겠긴 한데, 몇 번 그려보면 풀이 가능.

 

어떻게 배열이 채워지고 있는지 디버깅 해보며 시각화했다.

 

그리고 연결요소 즉, 리프노드까지 탐색 후 영역 개수 cnt++,

리프노드까지 탐색하는 동안 space++후 새로 갱신.

두 코드의 위치를 어디에 넣어야 할지 헤맸으나 어찌저찌 풀어냈다.

 

이제 dfs 코드는 안 보고도 줄줄 써내려갈 수 있도록 연마하기

---

CODE

#include <bits/stdc++.h>
using namespace std;

// input
const int max_m = 101;
int m, n, k, aa[max_m][max_m], a, b, c, d;

//result
int cnt,space;
vector<int> spc;

// dfs - connected component
bool visited[max_m][max_m];

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int dfs(int x, int y){
    visited[x][y] = 1;

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

        if(ny <0 || nx <0 || ny >=n || nx>= m) continue;
        if(aa[nx][ny] == 0 && !visited[nx][ny]){
            space++;
            dfs(nx,ny);
        }
    }
    return space;
}

int main()
{

    cin >> m >> n >> k;
    // a[m][n]
    //[b][a] ~ [d][c]

    for (int i = 0; i < k; i++)
    {
        cin >> a >> b >> c >> d;

        for (int x = b; x < d; x++)
        {
            for (int y = a; y < c; y++)
            {
                aa[x][y] = 1;
            }
        }
    }   

    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){

            //cout << aa[i][j] << " ";
            space = 1;
            if(aa[i][j]== 0 && !visited[i][j]){
                int k = dfs(i,j);
                cnt++;
                spc.push_back(k);
            }
        }
        //cout << '\n';
    }

    cout << cnt <<'\n';

    sort(spc.begin(), spc.end());

    for(int a : spc){
        cout << a <<" ";
    }
}

#include <bits/stdc++.h>
using namespace std;
#define y1 aaaa //키워드랑 겹쳐서! (y1, time 등이 있음)

int a[104][104], m, n, k, x1, x2, y1, y2, visited[104][104];
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
vector<int> ret;

int dfs(int y, int x)
{
    visited[y][x] = 1;
    int ret = 1;

    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || ny >= m || nx < 0 || nx >= n || visited[ny][nx] == 1)
            continue;
        if (a[ny][nx] == 1)
            continue;
        ret += dfs(ny, nx);
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> m >> n >> k;
    for (int i = 0; i < k; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        for (int x = x1; x < x2; x++)
        {
            for (int y = y1; y < y2; y++)
            {
                a[y][x] = 1;
            }
        }
    }
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (a[i][j] != 1 & visited[i][j] == 0)
            {
                ret.push_back(dfs(i, j));
            }
        }
    }
    sort(ret.begin(), ret.end());

    cout << ret.size() << "\n"; // ret의 사이즈로도 가능

    for (int a : ret)
        cout << a << " ";
    return 0;
}