글 읽기 - [C] 도와주세요 이 문제 맞추고 싶습니다 ㅠㅠ

maybe4444 2년 전 0

안녕하세요

뭐가 잘못된건지 찾을 수준이 안되는데 틀렸다고 나옵니다 ㅠㅠ

혹시 맞으려면 어디를 어떻게 수정 해야할까요? 도움 부탁드립니다....

#include <stdio.h>
#pragma warning(disable:4996)


int A[30][30]; //지도
int N; //가로,세로
int my[] = { -1,1,0,0 };
int mx[] = { 0,0,-1,1 };
int B[100]; //단지 수
int temp;

void DFS(int y, int x, int cnt) {

	int yy = 0;
	int xx = 0;

	for (int i = 0; i < 4; i++) {
		yy = y + my[i];
		xx = x + mx[i];

		//네방향 탐색 시작
		if (A[yy][xx] == 1) {
			A[yy][xx] = cnt;
			DFS(yy, xx, cnt);
		}
	}
}


int main() {

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

	int cnt = 2;                 //2부터 시작
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {

			if (A[i][j] == 1) {
				A[i][j] = cnt;
				DFS(i, j, cnt);
				cnt++;           //첫번째 단지는2로 찍고, 다음 단지는 +1함
			}

		}
	}
	
	//각 단지 몇개인지 세어보자
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			
			int t = 0;	
			if (A[i][j] >= 2) {
				t = A[i][j] - 1;
				B[t]++;
			}
		}
	}

 
	//오름차순으로 정렬
	for (int i = 0; i < N; i++) {
		for (int j = 1 + i; j <= N; j++) {
			
			if (B[i] == 0 || B[j] == 0) {
				//암것도 안함
			}
			else if (B[j] < B[i]) {
				temp = B[j];
				B[j] = B[i];
				B[i] = temp;
			}
		}
	}


	printf("%d\n", cnt - 2);
	for (int i = 1; i <= cnt-2; i++) {
		printf("%d\n", B[i]);
	}


	return 0;
}

cdh3261 2년 전 0

4방향 탐색할 때 경계선 넘어가는 것도 생각하셔야 해요.

euphoric_n 2년 전 1

1. DFS에서 범위를 넘어가는 경우를 고려하지 않습니다.

if(yy < 0 || yy >= N || xx < 0 || xx >= N) continue;

2. 단지를 최대 100개로 가정하셨는데

010101010101...

101010101010...

...

와 같은 입력이 나오면 313개까지도 나올 수 있습니다.

3. 오름차순 정렬에서 최대 단지 수 N개까지만 정렬하고 있습니다.

input :

01010

11011

00100

01010

10101

output :

1 1 1 3 3 1 1 1

answer :

1 1 1 1 1 1 3 3

maybe4444 2년 전 0

와.. 똑똑하고 친절하신 분들이 많네요!

집에가서 수정해서 다시 제출 해보겠습니다 감사합니다!

maybe4444 2년 전 0

1. 범위 넘어가는거 고려해서 if 문 추가했고

2. 단지 많은거 가정해서 수정했고, 단지 수 (100->700 수정함)

3. 오름차순 정렬 N개에서 cnt만큼(단지 갯수) 수정했습니다

근데 또 틀렸다고 하네요.. 하

토마토 지옥에서도 못 나왔는데 단지번호 지옥에 빠졌습니다 ㅠㅠ

#include <stdio.h>
#pragma warning(disable:4996)


int A[30][30]; //지도
int N; //가로,세로
int my[] = { -1,1,0,0 };
int mx[] = { 0,0,-1,1 };
int B[700]; //단지 수 (100->700 수정함)
int temp;

void DFS(int y, int x, int cnt) {

	int yy = 0;
	int xx = 0;
	for (int i = 0; i < 4; i++) {
		if (yy < 0 || yy >= N || xx < 0 || xx >= N) continue;   //범위 확인
			yy = y + my[i];
			xx = x + mx[i];

			//네방향 탐색 시작
			if (A[yy][xx] == 1) {
				A[yy][xx] = cnt;
				DFS(yy, xx, cnt);
			}
	}
}


int main() {

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

	int cnt = 2;                 //2부터 시작
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {

			if (A[i][j] == 1) {
				A[i][j] = cnt;
				DFS(i, j, cnt);
				cnt++;           //첫번째 단지는2로 찍고, 다음 단지는 +1함
			}

		}
	}

	//각 단지 몇개인지 세어보자
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {

			int t = 0;
			if (A[i][j] >= 2) {
				t = A[i][j] - 1;
				B[t]++;
			}
		}
	}


	//오름차순으로 정렬
	for (int i = 0; i < cnt; i++) {
		for (int j = 1 + i; j <= cnt; j++) {

			if (B[i] == 0 || B[j] == 0) {
				//암것도 안함
			}
			else if (B[j] < B[i]) {
				temp = B[j];
				B[j] = B[i];
				B[i] = temp;
			}
		}
	}


	printf("%d\n", cnt - 2);
	for (int i = 1; i <= cnt - 2; i++) {
		printf("%d\n", B[i]);
	}


	return 0;
}

euphoric_n 2년 전 1

17번 벗어나는 좌표 체크하는 부분이 잘못된 위치에 있네요.

yy = y + my[i];

xx = x + mx[i];

아래에 위치해야 합니다.

maybe4444 2년 전 0

@euphoric_n

너무너무너무 너무너무 감사드립니다 맞았습니다 ㅠㅠ

어떻게 하면 그렇게 잘 찾을 수 있나요 대단하십니다....

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

문제

문제

출처

ICPC

[C] 도와주세요 이 문제 맞추고 싶습니다 ㅠㅠ

maybe4444 2년 전 0

cdh3261 2년 전 0

euphoric_n 2년 전 1

maybe4444 2년 전 0

maybe4444 2년 전 0

euphoric_n 2년 전 1

maybe4444 2년 전 0

@euphoric_n

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말