글 읽기 - 뭐가 빠졌는지 잘 모르겠습니다,,

ash9452 3년 전 0

예제를 입력했더니 1 1 1 1 1 1 1 로 출력이 되네요,,

무엇을 추가해야되는지 무엇이 문제인지 잘 모르겠습니다ㅜㅜ

#include <iostream>
#include <algorithm>

using namespace std;

int n = 0; 
bool visit[25][25];  //방문한 집
int a[25][25] = { 0 };  //지도
int block[625] = { 0 }; //최대 단지수
int cnt = 0;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 }; // dy,dx 합친 좌표가 아래,왼,위,오른 순서

void dfs(int i, int j){
	visit[i][j] = true;
	block[cnt]++;

	for (int z = 0; z < 4; z++) { //상하좌우 집 확인
		int x = i + dx[z];
		int y = j + dy[z];
		if (a[x][y] == 1 && (visit[x][y] = !(true))) {
			dfs(x, y);
		}
	}
}

int main(void) {

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%1d", &a[i][j]);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if ((visit[i][j] != true) && a[i][j] == 1) {
				dfs(i, j);
				cnt++;
			}
		}
	}
	sort(block, block + 10);
	for (int i = 0; i < n; i++) {
		cout << block[i] <<endl;
	}
}

whs1999kr 3년 전 1

코드 확인후 답변드립니다.

프로그램이 정상적으로 작동하지 않았던 이유 중 가장 큰 이유는 28번째 라인의 visit[x][y] = !(true)입니다.

이 부분은 오타인거 같네요. 그리고 기타 수정해야 하는 부분이나 개선사항은 주석으로 남겨뒀어요.

#include <iostream>
#include <algorithm>

using namespace std;

int n = 0;
bool visit[25][25];  //방문한 집
int a[25][25] = { 0 };  //지도
int block[625] = { 0 }; //최대 단지수
int cnt = 0;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 }; // dy,dx 합친 좌표가 아래,왼,위,오른 순서

//좌표 범위 확인 함수 추가
inline bool checkCoord(int x, int y, int n) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

void dfs(int i, int j){
	visit[i][j] = true;
	block[cnt]++;

	for (int z = 0; z < 4; z++) { //상하좌우 집 확인
		int x = i + dx[z];
		int y = j + dy[z];
		//좌표 범위 확인 조건 추가
		//visit[x][y] = !(true) 가 아니라 visit[x][y] == !(true) 또는 !visit[x][y]가 되어야 한다.
		if (checkCoord(x, y, n) && a[x][y] == 1 && !visit[x][y]) {
			dfs(x, y);
		}
	}
}

int main(void) {

	cin >> n;

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visit[i][j] = false;
		}
	}


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
            //가독성을 위해 visit[i][j] != true는 visit[i][j] == false 또는 !visit[i][j]로 쓰는 것이 좋다.
			if (!visit[i][j] && a[i][j] == 1) {
				dfs(i, j);
				cnt++;
			}
		}
	}
	//cnt까지만 값이 들어와 있으므로 cnt까지만 정렬하면 된다.
	sort(block, block + cnt);
	//단지수 출력 추가
	cout << cnt << endl;
	//n까지가 아니라 cnt까지만 출력하면 된다.
	for (int i = 0; i < cnt; i++) {
		cout << block[i] <<endl;
	}
}

ash9452 3년 전 0

감사드립니다!

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

문제

문제

출처

ICPC

뭐가 빠졌는지 잘 모르겠습니다,,

ash9452 3년 전 0

whs1999kr 3년 전 1

ash9452 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말