인프런 커뮤니티 질문&답변

안녕하세요. 강사님

2-D 답안을 보면서 질문이 있습니다.

해설 강의에서 설명한 DFS 반환값 설정과 DFS 로직은 이미 이해한 상태에서 해당 문제를 접했는데요.

제가 답안을 보고 수정 및 작성한 코드는 아래입니다.

/*
답 : http://boj.kr/9815cd371fe643f59ac17a410e0cfca4
*/
#include <bits/stdc++.h>

using namespace std;

int M, N, K;
int m[104][104];
bool visited[104][104];
vector<tuple<int, int, int, int>> c;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int dfs(pair<int, int> node)
{
    int count = 1;

    visited[node.first][node.second] = true;

    for(int i = 0; i < 4; i++)
    {
        int nx = node.first + dx[i];
        int ny = node.second + dy[i];

        if(nx < 0 || nx >= N || ny < 0 || ny >= M)
            continue;
        if(!m[nx][ny] && !visited[nx][ny])
            count += dfs({nx, ny});
    }

    return count;
}

int main(void)
{
    cin >> M >> N >> K;

    for(int i = 0; i < K; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        c.push_back({x1, y1, x2, y2});
    }

    fill(&m[0][0], &m[0][0] + 104 * 104, 0);

    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            for(int k = 0; k < K; k++)
                if(get<0>(c[k]) <= i && i < get<2>(c[k]) && get<1>(c[k]) <= j  && j < get<3>(c[k]))
                    m[i][j] = 1;
        
    // for(int i = 0; i < N; i++)
    // {
    //     for(int j = 0; j < M; j++)
    //         cout << m[i][j];
    //     cout << '\n';
    // }

    int component = 0;
    vector<int> area;

    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            if(!m[i][j] && !visited[i][j])
            {
                component++;
                area.push_back(dfs({i, j}));
            }

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

    cout << component << '\n';
    for (int i = 0; i < area.size(); i++)
        cout << area[i] << ' ';
    cout << '\n';
    

    return 0;
}

저는 강사님과 약간 다르게 코드를 작성했는데 강사님의 이해를 돕기 위해 다른 점을 살짝 설명드리면

1. 해당 문제 예시 그림에서 시계 방향으로 90도 회전한 상태라고 가정하고 진행을 했습니다. 그래서 x, y 위치가 반대고 각 이중 for 문의 첫 for 문 내 조건문 표현식에서 N 을 사용합니다.

2. 미리 영역 좌표를 받고 int 형 데이터 4개를 가지고 있는 튜플을 사용했는데요.

제가 안되는 부분은 바로 해당 튜플을 가지고 영역을 표시할 때 입니다.

    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            for(int k = 0; k < K; k++)
                if(get<0>(c[k]) <= i && i < get<2>(c[k]) && get<1>(c[k]) <= j  && j < get<3>(c[k]))
                    m[i][j] = 1;

중요한건 오른쪽 위 좌표에 대해서 검사를 할 때 등호를 포함시키지 않는게 답을 위한 중요한 부분이였는데요.

이 부분이 이해가 가질 않습니다.