글 읽기 - 논리 오류

kimsy96 6년 전 0

이 문제를 2667번 단지 번호 붙이기 문제처럼 생각하고 풀었습니다.

왼쪽 아래부터 0,0인 경우여서 이걸 일반적인 (왼쪽 위가 0,0, 그옆이 0,1 ....) 경우로 바꾸려고 고민한 끝에

k를 입력 받고 좌표 두개(x좌표 y표 2개 총 4개) 입력 받을 때

그 순서를 바꾸어 넣어주면 일반적인 경우로 바뀔 수 있다고 생각했습니다. 배열을 0로 채운다음

문제에서 주어진 영역을 -1로 바꾸고

0인 부분을 bfs해서 "0인 부분의 단지번호 붙이기"

처럼 풀었는데 주어진 테스트케이스에서 이상한 값을 출력하네요

어디서 잘못됬을까요

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int arr[101][101];
int group[101][101];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int n,m;
int ans[25*25];
 void bfs(int x, int y, int cnt) {
     queue< pair<int,int> > q;
     q.push(make_pair(x,y));
     group[x][y] = cnt;
     while (!q.empty()) {
         x = q.front().first;
         y = q.front().second;
         q.pop();
         for (int k=0; k<4; k++) {
             int nx = x+dx[k];
             int ny = y+dy[k];
       

             if (0 <= nx && nx < m && 0 <= ny && ny < n) {
                 if (arr[nx][ny] == 0 && group[nx][ny] == 0) {
                     q.push(make_pair(nx,ny));
                     group[nx][ny] = cnt;
                 }
             }
         }
     }
 }
 int main() {
     int k;
     scanf("%d %d %d",&n,&m,&k);
     for(int i=0;i<k;i++)
     {
        int a,b,c,d;
        scanf("%d %d %d %d",&a,&b,&c,&d);
        for(int i=b;i<d;i++)
            for(int j=a;j<c;j++)
               arr[i][j]=-1;


     }
     int cnt = 0;
          for (int i=0; i<m; i++) {
         for (int j=0; j<n; j++) {
             if (arr[i][j] == 0 && group[i][j] == 0) {
                 bfs(i, j, ++cnt);
             }
         }
     }
     printf("%d\n",cnt);
     for (int i=0; i<m; i++) {
         for (int j=0; j<n; j++) {
             ans[group[i][j]]+=1;
         }
     }
     sort(ans+1, ans+cnt+1);
     for (int i=1; i<=cnt; i++) {
         printf("%d\n",ans[i]);
     }
     return 0;
 }