글 읽기 - (c++ bfs)도대체 어디가 틀린걸까요?

dkxm99 3년 전 0

전부 0일때도 해결해줬고 저 혼자 여러 예제를 만들어서 값을 넣어봐도 제대로된 답이 나옵니다. 근데 왜 제출만 하면 8%에서 컷당하는걸까요?

#include <iostream>
#include <queue>
#include <algorithm>
#define MAX 500+5

using namespace std;

int map[MAX][MAX];
int division[MAX * MAX];
bool visited[MAX][MAX];
int m, n, cnt, zeroCnt;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void bfs(int b, int a) {
	queue<pair<int, int>> q;
	q.push(make_pair(b, a));
	visited[b][a] = true;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || ny >= n || nx >= m)	continue;
			if (map[ny][nx] == 1 && !visited[ny][nx]) {
				visited[ny][nx] = true;
				division[cnt]++;
				q.push(make_pair(ny, nx));
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 1 && !visited[i][j]) {
				cnt++;
				division[cnt]++;
				bfs(i, j);
			}
		}
	}
	for (int i = 1; i <= cnt; i++) {
		if (division[i] == 0) {
			zeroCnt++;
		}
	}
	if (zeroCnt >= cnt) {
		cout << 0 << "\n";
		cout << 0;
	}
	else {		
		cout << cnt << "\n";
		sort(division + 1, division + (cnt + 1));
		cout << division[cnt];
	}
	return 0;
}

slah007 3년 전 1

#define MAX 500+5 로 하면 9줄의 MAX*MAX는 500+5*500+5 = 3005밖에 안됩니다. 항상 #define MAX (500+5)와 같이 괄호를 치는 것이 좋습니다.

dkxm99 3년 전 0

아하 저는 저렇게 해놔도 자동적으로 (500+5)*(500+5) 이렇게 될줄 알았는데 아니었나 보군요... 다음부턴 무조건 괄호 쳐놔야겠어요

slah007 3년 전 0

괄호가 귀찮으시면 const int MAX = 500+5로 하시면 됩니다 저는 #define보다는 const 써요

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

문제

문제

출처

ICPC

(c++ bfs)도대체 어디가 틀린걸까요?

dkxm99 3년 전 0

slah007 3년 전 1

dkxm99 3년 전 0

slah007 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말