글 읽기 - 도와주세요

gustjq1101 5년 전 0

질문게시판에 있는 제가 본 모든 케이스가 다 맞는데 왜 틀린지 제눈에 안보이네요..

방문하지 않은 지점에 dfs 함수를 돌리고 dfs함수가 연결된 노드 갯수를 반환하는 방식으로 만들었습니다.

마지막에 개행문자를 안넣은 테스트케이스가 있다고 해서 마지막에 개행문자도 빼봤습니다.

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

int data[25][25];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,1,-1};
int n;
vector<int> v;
int dfs(int i, int j, int cnt){
	data[i][j] = -1;
	cnt++;
	for(int k = 0; k < 4; k++){
		int ni = i + dx[k], nj = j + dy[k];
		if(ni < 0 || ni > n || nj < 0 || nj > n) continue;
		if(data[ni][nj] == 1) cnt = dfs(ni, nj, cnt);
	}
	return cnt;
}

int main() {
	cin >> n;
	for(int i = 0; i<n; i++){
		for(int j = 0; j<n; j++){
			scanf("%1d",&data[i][j]);
		}
	}
	for(int i = 0; i<n; i++){
		for(int j=0; j<n; j++){
			if(data[i][j] == 1){
					v.push_back(dfs(i,j,0));
			}
		}
	}
	sort(v.begin(),v.end());
	cout << v.size() << '\n';
	for(int i = 0; i<v.size(); i++){
		cout << v[i];
		if(i != v.size() - 1) cout << '\n';
	}
	return 0;
}

djm03178 5년 전 1

크기가 n이면 맵의 범위는 0~n-1까지입니다. 그래서 16번째 줄도 >= n으로 바꿔야 합니다. 안 그러면 최대 크기일 때 배열의 크기를 벗어나게 됩니다.

djm03178 5년 전 2

그리고 마지막에 개행 문자를 안 넣은 케이스가 있다는 것은 입력 파일이 그랬다는 것이고 출력하고는 아무 관련 없습니다. 그것도 이미 수정된 상황입니다.

djm03178 5년 전 0

눈으로 보이는 반례도 하나 드립니다.

25
0000000000000000000000001
1000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000

gustjq1101 5년 전 0

헐 감사합니다. 어이없는 실수였네요...

범위 수정하고 돌리니까 맞았습니다 ㅎㅎ

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

문제

문제

출처

ICPC

도와주세요

gustjq1101 5년 전 0

djm03178 5년 전 1

djm03178 5년 전 2

djm03178 5년 전 0

gustjq1101 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말