글 읽기 - C++ 2667 (주석있음)

kimin0626 2년 전 0

틀렸다고 뜨는데, 반례가 있을까요?

제가 임의로 만든 테스트케이스에서는 다 잘 되는데 제출만하면 틀렸다고하네요 ㅠ

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstdio>
using namespace std;

int n; //지도의 크기 nxn
vector<vector<int>> graph(25,vector<int>(25,0)); //지도
int d[25][25]; //방문했는지 체크
int cnt=0; // 단지의 개수
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int sum[16]={0, }; //각 단지의 집의 개수를 넣을 배열

void reset(){ // 방문기록을 0으로..
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      d[i][j]=0;
    }
  }
}

void bfs(int x,int y,int cnt){
  queue<pair<int,int>> q;
  q.push(make_pair(x,y));
  d[x][y]=cnt;
  while(!q.empty()){
    x=q.front().first; y=q.front().second;
    q.pop();
    for(int i=0;i<4;i++){
      int nx=x+dx[i]; int ny=y+dy[i];
      if(0<=nx&&nx<n && 0<=ny&&ny<n)
        if(graph[nx][ny]==1&&d[nx][ny]==0){
          q.push(make_pair(nx,ny));
          d[nx][ny]=cnt;
        }
    }
  }
}

void danji(int c){  //지도를 다 돌면서 c와같은값이 있으면 1추가하는 함수
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(d[i][j]==c)
        sum[c]++;
    }
  }
}

int main()
{
  scanf("%d",&n); //지도크기 입력
  for(int i=0;i<n;i++){ //지도 입력 구간
    for(int j=0;j<n;j++){
      scanf("%1d",&graph[i][j]);
    }
  }
  reset();
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(graph[i][j]==1&&d[i][j]==0){ //집이있고, 방문한적이 없으면..
        bfs(i,j,++cnt);
        danji(cnt); //cnt단지에 해당하는 집들의 개수를 세어봄
      }
    }
  }
  printf("%d\n",cnt);
  sort(sum,sum+(cnt+1)); 
  for(int k=1;k<=cnt;k++){
    printf("%d\n",sum[k]);
  }
}

0000000000 2년 전 0

(공간을 너무 많이 잡아먹어서 지우고 다시 씁니다)

sum배열의 크기가 부족한 경우가 생깁니다.

input:

25
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

참고로 답은 첫줄에 313, 둘째 줄부터 314번째 줄까지 1이 찍혀야 합니다.

kimin0626 2년 전 0

말씀해주신거 반영해서 sum을 아예 sum[1000]으로 잡았는데요 그래도 틀렸다고 뜨네요.. 제공해주신 테스트케이스는 통과됩니다 ㅠ

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstdio>
using namespace std;

int n; //지도의 크기 nxn
vector<vector<int>> graph(25,vector<int>(25,0)); //지도
int d[25][25]; //방문했는지 체크
int cnt=0; // 단지의 개수
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int sum[1000]={0, }; //각 단지의 집의 개수를 넣을 배열

void reset(){ // 방문기록을 0으로..
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      d[i][j]=0;
    }
  }
}

void bfs(int x,int y,int cnt){
  queue<pair<int,int>> q;
  q.push(make_pair(x,y));
  d[x][y]=cnt;
  while(!q.empty()){
    x=q.front().first; y=q.front().second;
    q.pop();
    for(int i=0;i<4;i++){
      int nx=x+dx[i]; int ny=y+dy[i];
      if(0<=nx&&nx<n && 0<=ny&&ny<n)
        if(graph[nx][ny]==1&&d[nx][ny]==0){
          q.push(make_pair(nx,ny));
          d[nx][ny]=cnt;
        }
    }
  }
}

void danji(int c){  //지도를 다 돌면서 c와같은값이 있으면 1추가하는 함수
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(d[i][j]==c)
        sum[c]++;
    }
  }
}

int main()
{
  freopen("input.txt", "r", stdin);
  scanf("%d",&n); //지도크기 입력
  for(int i=0;i<n;i++){ //지도 입력 구간
    for(int j=0;j<n;j++){
      scanf("%1d",&graph[i][j]);
    }
  }
  reset();
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(graph[i][j]==1&&d[i][j]==0){ //집이있고, 방문한적이 없으면..
        bfs(i,j,++cnt);
        danji(cnt); //cnt단지에 해당하는 집들의 개수를 세어봄
      }
    }
  }
  printf("%d\n",cnt);
  sort(sum,sum+(cnt+1)); 
  for(int k=1;k<=cnt;k++){
    printf("%d\n",sum[k]);
  }
}

0000000000 2년 전 1

bfs()에서 d[nx][ny]를 cnt가 아닌 d[x][y]+1로 해 주셔야 합니다.

또한 sum배열에는 1-index로 값이 저장되어 있기 때문에 sort()에서 시작 주소로 그냥 sum을 보내는 게 아닌 sum+1을 보내야 합니다.

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

문제

문제

출처

ICPC

C++ 2667 (주석있음)

kimin0626 2년 전 0

0000000000 2년 전 0

kimin0626 2년 전 0

0000000000 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말