글 읽기 - 모든 것이 1인 경우 출력을 안하는데 어떻게 처리를 할까요? + dfs질문

specimen 5년 전 0

예전에 bfs로 풀었다가

dfs가 너무 약한거 같아서 다시 풀어보고 있습니다.

질문 게시판을 돌아다니면서

여러 예제들을 넣어 봤는데 잘 나옵니다.

그래서

111

이렇게 넣어봤는데

가 나와야 되지 않나요? 그런데

0을 출력을 하네요.

소스 어느 부분이 틀린건지 고수님들 도움 좀 부탁드립니다.

그리고 다른 분들 dfs를 보면 되게 간단하게 소스도 짧게 짜시더라구요.

그런데 재귀를 이해하는데 아직도 시간이 필요한 것 같아서. bfs 짜듯이 방향을 줘서(const int dy, dx 선언) 이런식으로 짰는데

이런 식으로 짜도 큰 상관이 없을지 궁금합니다.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl "\n";
const int dy[4] = {-1, 1, 0, 0};
const int dx[4] = {0, 0, -1, 1};
int map[26][26];
int check[26][26];
int T;
int cnt = 1;
int totalNumber[25];

void Init(){
    for(int i = 0; i < T; i++){
        for(int j = 0; j < T; j++){
            check[i][j] = 0;
        }
    }
}

void Print(){
    for(int i = 0; i < T; i++){
        for(int j = 0; j < T; j++){
            totalNumber[map[i][j]]++;
        }
    }
    cout << cnt - 1 << endl;
    sort(totalNumber, totalNumber + cnt + 1);
    for(int i = 1; i < cnt; i++){
        cout << totalNumber[i] << endl;
    }
}

void Dfs(int y, int x, int cnt){
    map[y][x] = cnt;
    check[y][x] = true;
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny >= 0 && ny < T && nx >= 0 && nx < T){
            if(check[ny][nx] == 0 && map[ny][nx] == 1) {
                Dfs(ny, nx, cnt);
                map[ny][nx] = cnt;
            }
        }
    }
}

void Solution(){
    for(int i = 0; i < T; i++){
        for(int j = 0; j < T; j++){
            if(check[i][j] == 0 && map[i][j] == 1){
                Dfs(i, j, cnt);
                cnt++;
            }
        }
    }
}

void Input(){
    for(int i = 0; i < T; i++){
        for(int j = 0; j < T; j++){
            scanf("%1d", &map[i][j]);
        }
    }
}

int main(void){
    cin >> T;

    Input();
    Init();
    Solution();
    Print();
}

kyo20111 5년 전 0

일단 29번째 줄의 sort가 이상하네요. 저 소트의 범위를 보면 0 ~ cnt까지 저장되어 있는 수를 정렬하는데, 코드를 읽어보면 1~cnt-1를 정렬해야합니다.

specimen 5년 전 0

답변 감사드립니다. 수정후

여러 케이스를 넣었는데 잘 나옵니다.

음.. 뭐가 계속 틀린걸까요 ㅠㅠ

1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101

같은게 나올수있는데 과연 배열의 최대크기가 25로 충분할까요?

djm03178 5년 전 2

왜 현재 코드가 예제는 잘 나왔냐 하면, map[i][j]가 0인 곳이 가장 많아서 totalNumber를 0까지 포함해서 정렬해도 cnt번째로 넘어갔기 때문에 출력이 되지 않아서 그랬을 뿐입니다. 3 111 111 111 예제에서는 0이 하나도 없기 때문에 0번째에 위치하게 되고, cnt번째인 2도 totalNumber[2] 역시 0이기 때문에 1번째에 위치하고, totalNumber[1]은 9였기 때문에 totalNumber[2]가 되면서 출력 범위에 들어가지 않게 된 것입니다.

sort 범위를 totalNumber + 1, totalNumber + cnt로 하고, totalNumber의 크기를 1000으로 늘리면 맞습니다.

specimen 5년 전 0

와우 답변 감사드립니다.!! 크기도 문제 였네요 !!

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

문제

문제

출처

ICPC

모든 것이 1인 경우 출력을 안하는데 어떻게 처리를 할까요? + dfs질문

specimen 5년 전 0

kyo20111 5년 전 0

specimen 5년 전 0

kyo20111 5년 전 0

djm03178 5년 전 2

specimen 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말