글 읽기 - 반례가 있는건가요? 어디가 틀린지 모르겠습니다.

yuhj0214 4년 전 0

게시판에 있는 여러 반례들을 넣어봐도 잘 작동하는데 왜 틀렸다고 뜨는지 모르겠습니다.

처음 질문 남겨보는거라 조심스러운데, 제가 잘못 질문한점도 있으면 지적 부탁드립니다!

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int apt[25][25];
vector<int> graph[25*25];
int check[25*25];
int acount;
vector<int> aacount;
void dfs(int start){
  check[start] = 1;
  for (int i = 0; i < graph[start].size(); i++){
    int next = graph[start][i];
    if (check[next] == -1) {
        dfs(next);
        acount += 1;
    }
  }
}
int main(){
  int n;
  cin >> n;
  for(int i = 0; i<n; i++){
    for(int j = 0; j<n; j++){
      scanf("%1d", &apt[i][j]);
      if(i-1 >= 0 && apt[i-1][j] == 1 && apt[i][j] == 1){
        graph[(i-1)*n+j].push_back((i*n)+j);
        graph[(i*n)+j].push_back((i-1)*n+j);
        check[(i-1)*n+j] = check[(i*n)+j] = -1;
      }
      if(j-1 >= 0 && apt[i][j-1] == 1&& apt[i][j] == 1){
        graph[i*n+(j-1)].push_back((i*n)+j);
        graph[(i*n)+j].push_back(i*n+(j-1));
        check[i*n+(j-1)] = check[(i*n)+j] = -1;
      }
    }
  }
  int count = 0;
  for(int i = 0; i<n*n; i++){
    if(check[i] == -1){
      count += 1;
      acount = 1;
      dfs(i);
      aacount.push_back(acount);
    }
  }
  cout << count << "\n";
  sort(aacount.begin(), aacount.end());
  for(int i = 0; i<aacount.size(); i++){
    cout << aacount[i] << "\n";
  }
  return 0;
}

yuhj0214 4년 전 0

집이 한개만 존재해도 단지가 이루어지는 점을 파악하지 못했네요!

해결했습니다!!

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

문제

문제

출처

ICPC

반례가 있는건가요? 어디가 틀린지 모르겠습니다.

yuhj0214 4년 전 0

yuhj0214 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말