글 읽기 - BFS 무엇이 틀렸을까요

luciferkala 4년 전 0

피드백 부탁드립니다

어떤 반례가 있는지 잘 모르겠습니다

#include <stdio.h>
#include <queue>

using namespace std;

int n;
struct h {
  int y;
  int x;
};
int map[26][26] = {0};
int visited[26][26] = {0};
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};

void BFS(int starty, int startx, int count) {
  queue<h> q;
  h h1 = {starty,startx};
  q.push(h1);
  
  while(!q.empty()) {
    h now = q.front();
    int nowy = now.y;
    int nowx = now.x;
    q.pop();
    if(map[nowy][nowx] == 1) map[nowy][nowx] = count;
    for(int d = 0; d < 4; d++) {
        int nexty = nowy + dc[d];
        int nextx = nowx + dr[d];
        if(nexty < 0 || nextx < 0 || nexty > n || nextx > n) continue;
        if(map[nexty][nextx] == 0) continue;
        if(map[nexty][nextx] == 1 && visited[nexty][nextx] == 0) {
        h next;
        next.y = nexty;
        next.x = nextx;
        q.push(next);
        visited[nexty][nextx] = count;
        }
    }
  }
}

int main() {
  int ap = 1;
  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 && visited[i][j] == 0)
          BFS(i,j, ap++);
    }
  }

  // for(int i = 1; i <= n; i++) {
  //   for(int j = 1; j <= n; j++) {
  //     printf("%1d ", visited[i][j]);
  //   }
  //   printf("\n");
  // }
  printf("%d\n", ap-1);
  int* answer = new int[ap];
  
   for(int i = 1; i <= n; i++) {
     for(int j = 1; j <= n; j++) {
         if(map[i][j] > 0)
           answer[map[i][j]]++;
     }
   }
   for(int i = 1; i < ap; i++)
     if(answer[i]) printf("%d\n", answer[i]);
  return 0;
}

tristan3716 4년 전 1

그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

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

문제

문제

출처

ICPC

BFS 무엇이 틀렸을까요

luciferkala 4년 전 0

tristan3716 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말