글 읽기 - dfs 로 작성하였는데 어디가 틀린 부분인지 모르겠습니다.

unilep 6년 전 0

안녕하세요

a[i][j] 가 0 보다 크고 방문하지 않은 곳 을 dfs돌려서

dx, dy 로 주위에 방문이 가능한 경우 m[ans] 를 1씩 더해주는 방식으로 했습니다

마지막에 m을 정렬하고 m[i] 를 출력했습니다

#include<iostream>
#include<algorithm>
using namespace std;

int a[30][30];
char str[30];
bool visit[30][30];
int m[30];
int N;

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

void dfs(int x, int y, int ans) {
	visit[x][y] = true;
	m[ans]++;

	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 && !visit[nx][ny] && a[nx][ny] == 1)
			dfs(nx, ny, ans);
	}
}

int main() {
	ios::sync_with_stdio(false);
	int ans = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> str;
		for (int j = 0; j < N; j++) {
			a[i][j] = str[j] - '0';
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (a[i][j] > 0 && !visit[i][j]) {
				dfs(i, j, ans++);
			}
		}
	}

	sort(m, m + ans);
	cout << ans << endl;
	for (int i = 0; i < ans; i++) {
		cout << m[i] << endl;
	}
}

ehddml3 6년 전 0

단지수가 최대 몇개일까요?

unilep 6년 전 0

최대 25개 입니다.

힌트를 주신거 같은데 의미를 잘 모르겠습니다 ㅜㅜ

ehddml3 6년 전 2

0 1 0 1 0 1 0 1

1 0 1 0 1 0 1 0

...

n=25이고 이런 방식이면용?

unilep 6년 전 1

감사합니다. 해결되었습니다!!

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

문제

문제

출처

ICPC

dfs 로 작성하였는데 어디가 틀린 부분인지 모르겠습니다.

unilep 6년 전 0

ehddml3 6년 전 0

unilep 6년 전 0

ehddml3 6년 전 2

unilep 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말