글 읽기 - 반례가 존재하나요? ㅠㅠ 단지번호붙이기 문제요

muselism 5년 전 0

테스트케이스 올려주신거 몇개 실행해봐도 잘 돌아가는데 틀렸습니다가 뜨는 이유가 뭔지 모르겠습니다. ㅠㅠ

구현은 dfs로 하였습니다.

반례찾아주시면 정말 감사하겠습니다 형님들 ㅠㅠ

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>

#define MAX 10000
using namespace std;

vector<int> graph[MAX];
bool visit[MAX];
int num[1000], idx = -1;

void dfs(int start) {
    visit[start] = true;

    int next; 
    for(int i = 0; i < graph[start].size(); i++) {
        next = graph[start][i];
        if(!visit[next]) {
            num[idx]++;
            dfs(next);
        }
    }
}

int main() {
    char str[MAX];
    char tmp[30];
    int n, cnt = 0;

    scanf("%d", &n);
    int whole = n * n;
    for(int i = 0; i < n; i++) {
        scanf("%s", tmp);
        !i ? strcpy(str, tmp) : strcat(str, tmp); 
    }

    for(int i = 0; i < whole; i++) {
        if(str[i] == '0') continue;
        if(i % n != 0 && i >= 1 && str[i - 1] == '1') graph[i].push_back(i - 1);
        if(i >= n && str[i - n] == '1') graph[i].push_back(i - n);
        if(i + 1 % n != 0 && i < whole && str[i + 1] == '1') graph[i].push_back(i + 1);
        if(i < whole - n && str[i + n] == '1') graph[i].push_back(i + n);
    }
    for(int i = 0; i < whole; i++) {
        if(!visit[i] && str[i] == '1') {
            cnt++; idx++;
            dfs(i);
        }
    }

    printf("%d\n", cnt);
    sort(num, num + cnt);
    for(int i = 0; i < idx + 1; i++) {
        printf("%d\n", num[i] + 1);
    }
}

windflower 5년 전 0

틀린 이유는 잘 모르겠지만 visit배열 초기화 해 주셨으면 좋겠어요! (운 나쁘게 쓰레기값으로 1이 들어갈 수 있으니까요)

cubelover_dev 5년 전 2

입력

출력

muselism 5년 전 0

감사합니다!

세번째 if문의 조건식

i + 1 % n != 0

에서 연산순서가 1 % n 부터 되는 것이 문제였습니다.

(i + 1) % n != 0 으로 고치니 해결되었습니다!

아 그리고 세번째 if문의 두번째 조건식인 i < whole 도 i < whole - 1로 수정하였습니다.

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

문제

문제

출처

ICPC

반례가 존재하나요? ㅠㅠ 단지번호붙이기 문제요

muselism 5년 전 0

windflower 5년 전 0

cubelover_dev 5년 전 2

muselism 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말