글 읽기 - dfs로 구현하는데 게시판 반례들은 다 적용해봤는데 무엇이 잘못된걸까요?

kangsy763 4년 전 0

bfs로 한 번 구현을 해보고 통과를해서dfs로 구현해보았는데 맞다고 생각이 든 코드였는데 오답이 나오길레 반례들을 많이 집어넣어봤는데도 다 통과를 해서 글을 올리게 되었습니다. 어느부분이 문제인지 알고싶습니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int map[26][26];
int visit[26][26];
int group_id = 1;
int group[500];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void dfs(int x, int y) {
	visit[x][y] = 1;
	group[group_id]++;
	for (int i = 0; i < 4; i++) {
		int xx = x + dx[i];
		int yy = y + dy[i];
		if (xx > 0 && xx <= n && yy > 0 && yy <= n) {
			if (map[xx][yy] != 0 && visit[xx][yy] == 0) dfs(xx, yy);
		}
	}
}

int main() {
	int n;
	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] != 0 && visit[i][j] == 0) {
				dfs(i, j);
				group_id++;
			}
		}
	}
	group_id--;
	sort(group + 1, group+1+group_id);
	printf("%d\n", group_id);
	for (int i = 1; i <= group_id;i++) {
		printf("%d\n", group[i]);
	}
	return 0;
}

1207koo 4년 전 1

18번째 줄에 분명 yy<n이었던 것 같은데...뭐 암튼 이거는 문제가 아니고

25번째 줄을 봐주세요

kangsy763 4년 전 1

올리고 보니깐 < 이길레 수정했었어요 ㅋㅋㅋ

아... 참 저게 왜 int n이 또 있는지 ㅜㅜㅜ 감사합니다 희안한게 저 코드그대로로 테스트케이스 통과가 안되는데 제가 테스트케이스 할 떄에 bfs로 했던건지.. 그땐 어케 테스트케이스가 제대로 나왔찌... 어쩃든 감사합니다

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

문제

문제

출처

ICPC

dfs로 구현하는데 게시판 반례들은 다 적용해봤는데 무엇이 잘못된걸까요?

kangsy763 4년 전 0

1207koo 4년 전 1

kangsy763 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말