글 읽기 - BFS 틀린 부분 봐주세요 ㅠ

luciferkala 4년 전 0

오름차순 정렬도 했는데 틀림이 나와서.... 어떤 부분이 문제일지 궁금합니다

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
int n;
struct h {
    int y;
    int x;
};
int map[25][25] = {0};
int visited[25][25] = {0};
int cnt;
int dc[4] = {0,0,1,-1};
int dr[4] = {1,-1,0,0};

void BFS(int starty, int startx, int cnt) {
  queue<h> q;
  h h1;
  h1.y = starty;
  h1.x = startx;
  q.push(h1);

  
  while(!q.empty()) {
      int nowy = q.front().y;
      int nowx = q.front().x;
      q.pop();
      visited[nowy][nowx] = cnt;
      for(int i = 0; i < 4; i++) {
          int nexty = nowy + dc[i];
          int nextx = nowx + dr[i];
          if(nexty < 0 || nexty >= n || nextx < 0 || nextx >= n) continue;
          if(map[nexty][nextx] == 0 || visited[nexty][nextx] != 0) continue;
          h h2 = {nexty,nextx};
          q.push(h2);
      }
  }
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    cnt = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(map[i][j] == 1 && visited[i][j] == 0) BFS(i,j,++cnt);
        }
    }
    
    // for(int i = 0; i < n; i++) {
    //   for(int j = 0; j < n; j++) {
    //         printf("%d ", visited[i][j]);
    //     }
    //     printf("\n");
    // }
    
    int* ans = new int[cnt];
    
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
            if(visited[i][j] > 0) ans[visited[i][j]-1]++;
        }
    }
    sort(ans, ans+cnt);
    
    printf("%d\n", cnt);
    for(int i = 0; i < cnt; i++)
        printf("%d\n", ans[i]);
}

tristan3716 4년 전 0

ans[0]에는 어떤 값이 들어있을까요?

int* ans = new int[cnt];

tristan3716 4년 전 0

그리고 큐에서 꺼낼 때 방문 여부를 기록하고 있는데, 방문 여부를 확인하고 있지 않습니다.

따라서 방문한 좌표를 또 방문하게 되어 방문 횟수는 약 4^N이 되게됩니다.

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

문제

문제

출처

ICPC

BFS 틀린 부분 봐주세요 ㅠ

luciferkala 4년 전 0

tristan3716 4년 전 0

tristan3716 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말