글 읽기 - 반례 부탁드립니다.

dhffpt83 3년 전 0

N = 정사각형의 한 변의 크기

f는 단지 번호(ex. 1단지, 2단지)

map[27][27] = 땅, visit[27][27] = 땅 방문 여부

adj[27][27] = 좌표에 인접한 아파트의 좌표 (좌표 i, j에 인점한 아파트가 왼쪽 뿐이라면 daj[i][j]에는 pair[i-1][j]밖에 없는 식으로요)

danji[1001] = danji[n]이라면 n단지에는 danji[n]만큼의 아파트 수가 있다.

maze함수는 고수분들은 이해하실겁니다ㅠㅠ

테스트 케이스는 맞게 나오는데 분명 반례가 있겠지요ㅠㅠ.

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
int N, f=0, map[27][27], visit[27][27];
vector<pair<int, int>> adj[27][27];
int danji[1001];

void maze(int x, int y){
  f++;
  pair<int, int> z(x, y);
  pair<int, int> w;
  queue<pair<int, int>> q;
  q.push(z);
  while(!q.empty()){
    z = q.front();
    visit[z.first][z.second] = 1;
    danji[f]++;
    q.pop();
    x = z.first; y = z.second;
    for(int i=0; i<adj[x][y].size(); i++){
      w = adj[x][y][i];
      if(visit[w.first][w.second] == 0){
        q.push(w);
        visit[w.first][w.second] = 1;
      }
    }
  }
}

int main() {
  scanf("%d", &N);
  for(int i=1; i<=N; i++){
    for(int j=1; j<=N; j++){
      scanf("%1d", &map[i][j]);
    }
  }
  for(int i=1; i<=N; i++){
    for(int j=1; j<=N; j++){
      if(map[i][j] == 1){
        if(map[i+1][j] == 1){adj[i][j].push_back(pair<int, int>(i+1, j));}
        if(map[i-1][j] == 1){adj[i][j].push_back(pair<int, int>(i-1, j));}
        if(map[i][j-1] == 1){adj[i][j].push_back(pair<int, int>(i, j-1));}
        if(map[i][j+1] == 1){adj[i][j].push_back(pair<int, int>(i, j+1));}
      }
      else if(map[i][j] == 0){visit[i][j] = 1;}
    }
  }
  for(int i=1; i<=N; i++){
    for(int j=1; j<=N; j++){
      if(visit[i][j] == 0){ maze(i, j);}
    }
  }
  int n=1;
  while(danji[n] != 0){n++;} n -= 1;
  printf("%d\n", n);
  for(int i=1; i<=n; i++){
    printf("%d\n", (int)danji[i]);
  }
}

kms9937 3년 전 2

반례입니다.

input:

5
11100
01000
11010
01010
00111

answer:
2
5
7
wrong answer:
2
7
5

kms9937 3년 전 2

그리고 오름차순 정렬을 안해 주신것 같습니다.(아마 이때문에 틀리신것 같네요.)

dhffpt83 3년 전 0

아 문제를 또 제대로 안읽었네요 감사합니다. 덕분에 다시 해서 맞췄어요

lgj125 3년 전 0

같은 오류땜에 도움됐어용

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

문제

문제

출처

ICPC

반례 부탁드립니다.

dhffpt83 3년 전 0

kms9937 3년 전 2

kms9937 3년 전 2

dhffpt83 3년 전 0

lgj125 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말