글 읽기 - 다시 푸는데 논리적 오류가 있는지 안 풀리네요.

playscer 2년 전 0

dfs를 처음 할 때마다 벡터에 넣는식으로 구현을 하였는데...output이 잘 안 나오네요. 로직은 맞는거 같은데 무엇을 잘못했는지 모르겠습니다.

#include <cstdio>
#include <algorithm>
#include <vector>

const int MAX = 30;

using namespace std;

int n;
int arr[MAX][MAX]={0,};
bool visited[MAX][MAX] = { 0, };
vector <int> v;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int cnt = 1;

int dfs(int x, int y) {
	cnt = 1;
	visited[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
			if (!visited[nx][ny] && arr[nx][ny] == 1) {
				cnt += dfs(nx, ny);
			}
		}
	}
	return cnt;
}


int main() {
	
	

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}

	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 1 && !visited[i][j]) {
				v.push_back(dfs(i, j));
			}
		}
	}
	sort(v.begin(), v.end());
	printf("%d\n", v.size());
	for (int i = 0; i < v.size(); i++) {
		printf("%d\n", v[i]);
	}



	return 0;
}

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

문제

문제

출처

ICPC

다시 푸는데 논리적 오류가 있는지 안 풀리네요.

playscer 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말