글 읽기 - vector 에 문제가 있는건지 궁금합니다.

dhwhc0711 3년 전 1

DFS 가 제대로 동작하지 않는 것 같습니다.

구역으로 나뉘어서 13 7 1 로 나와야 한다면 한 꺼번에 더한 값인 21이 나옵니다.

DFS가 제대로 동작하는지 확인하기 위해서 매 DFS 마다 map을 출력하려 했으나

0 0 0 0 1 1 0
0 1 0 0 1 1 0
1 1 1 1 0 0 0
1 1 1 1 0 0 0
0 1 0 0 0 0 0

으로 나오던 맵이 DFS 코드 안에서는

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

이런 식으로 나오네요;;

조언 부탁드립니다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
int N, M;
int mx[4] = {0, 0, 1, -1};
int my[4] = {1, -1, 0, 0};
int cnt = 0;

void init()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void dfs(int r, int c, vector<vector<int>> &map)
{
    map[r][c] = 1;
    cnt++;

    for (int i = 0; i < 4; i++)
    {
        int nr = r + mx[i];
        int nc = c + my[i];

        if (nr < 0 || nc < 0 || nr >= M || nc >= N)
        {
            continue;
        }

        if (map[nr][nc] == 0)
        {
            dfs(nr, nc, map);
        }
    }
}

int main()
{
    init();
    int M, N, K;
    cin >> M >> N >> K;
    vector<vector<int>> map(M, vector<int>(N, 0));
    vector<int> answer;

    // 모눈종이에 직사각형 그리기 (문제 x)
    for (int i = 0; i < K; i++)
    {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        for (int j = y1; j < y2; j++)
        {
            for (int k = x1; k < x2; k++)
            {
                map[j][k] = 1;
            }
        }
    }

    // // 격자 출력
    // for (int i = 0; i < M; i++)
    // {
    //     for (int j = 0; j < N; j++)
    //     {
    //         cout << map[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    // 격자 탐색하기
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] == 0)
            {
                cnt = 0;
                dfs(i, j, map);
                answer.push_back(cnt);
            }
        }
    }

    sort(answer.begin(), answer.end());
    cout << answer.size() << "\n";

    for (auto idx : answer)
    {
        cout << idx << " ";
    }
}

nahwasa 3년 전 0

벡터엔 문제없구..

힌트는

int M, N, K;

여기에 문제 있습니다.

+ algorithm include 필요합니다.

dhwhc0711 3년 전 1

@nahwasa

정말 감사합니다ㅠㅠㅠㅠㅠ 실수 줄이도록 노력해봐야 할 것 같습니다

귀중한 시간 내주셔서 정말 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

vector 에 문제가 있는건지 궁금합니다.

dhwhc0711 3년 전 1

nahwasa 3년 전 0

dhwhc0711 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말