글 읽기 - [백준11724 / C++] 왜 틀렸는지 모르겠습니다. 도와주세요....!

goodluck616 3년 전 0

안녕하세요. DFS, BFS 이외의 방법으로 이 문제를 풀어보려고 아래와 같은 코드를 작성했는데요.

문제의 예시 케이스와 게시판에 올라온 모든 반례들을 다 통과했는데 채점 결과 매번 틀렸다고 나옵니다ㅜ.ㅜ

어디서 잘못된 것일까요....? 고수님들의 도움을 부탁드립니다!😥

#ifndef _CRT_SECURE_NO_WARNINGS 
#define _CRT_SECURE_NO_WARNINGS 
#endif
#include <stdio.h>

int main(void) {
	int m, n, m1, m2, max, count, num, compare, decide;
    /* count는 연결 요소의 갯수를 담는 변수, num은 입력된 값의 갯수를 담는 변수 */
	count = num = 0;
    
	scanf("%d %d", &m, &n);
    
	max = m; // 반복문이 돌아가야 하는 최대값을 알기 위한 변수 max
	int l[1001] = { 0, }; // 꼭지점들을 나타내는 배열
	int check[1001] = { 0, }; // 입력 여부를 점검하는 배열
    
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &m1, &m2);
        
        /* m1이나 m2 중 max보다 더 큰 값이 입력되면 max를 그 값으로 변경 */
		if (m1 > max) {
			max = m1;
		}
		if (m2 > max) {
			max = m2;
		}
        
        /* 방문 여부가 표시되지 않았을 경우 표시하고 num 증가 */
		if (check[m1] == 0) {
			check[m1] = 1;
			num++;
		}
		if (check[m2] == 0) {
			check[m2] = 1;
			num++;
		}
        
        /* 두 꼭지점 모두 처음 연결되는 경우에는 count를 1 증가시키고 양쪽 꼭지점에 모두 넣어줌 */
		if (l[m1] == 0 and l[m2] == 0) 
			count++;
			l[m1] = count;
			l[m2] = count;
		}
        
        /* 한 꼭지점이 다른 그래프에 붙는 경우에는, 그 그래프의 count 값을 새로 들어오는 꼭지점에 넣어줌 */
		else if (l[m1] == 0 and l[m2] != 0) {
			l[m1] = l[m2];
		}
		else if (l[m1] != 0 and l[m2] == 0) {
			l[m2] = l[m1];
		}
        
        /* 서로 다른 그래프가 연결될 경우 count 값을 1 내리고 두 그래프의 count 값을 동일하게 맞춰줌 */
		else {
			if (l[m1] == l[m2]) continue;
			else {
				count--;
				if (l[m1] < l[m2]) {
					decide = l[m1];
					compare = l[m2];
				}
				if (l[m1] > l[m2]) {
					decide = l[m2];
					compare = l[m1];
				}
				for (int j = 1; j < m + 1; j++) {
					if (l[j] == compare) {
						l[j] = decide;
					}

				}

			}

		}
	}

    /* n이 0인 경우에는 모든 꼭지점 하나하나가 연결 요소이므로 m을 출력 */
	if (n == 0) {
		printf("%d", m);
	}

    /* n이 0이 아닌 경우에는 연결된 그래프와 연결되지 않은 꼭지점 갯수의 합산을 출력 */
	else {
		int zero = 0;
		for (int i = 1; i <= max; i++) {
			if (l[i] == 0 && check[i] == 1) zero++;
		}
		printf("%d", count+zero+(m-num));
	}
}

sonjaewon 3년 전 1

어 dfs 써야하는 문제 아닌가요?

goodluck616 3년 전 0

네 그런데 dfs 이외의 방법으로도 풀 수 있을 것 같아서 저렇게 해 보았습니다....! 그런데 문제랑 게시판에 있는 케이스들을 다 통과하는데도 채점 결과 틀렸다고 나오네요ㅜ.ㅜ 무엇이 문제일까요....?

sonjaewon 3년 전 2

어... 글쎄요? DFS 로 푸는게...

어쨌든 39번째 줄 if 문에 괄호가 하나밖에 없는데요?

그건 그렇게 큰 문제가 되진 않을 것 같네요

goodluck616 3년 전 0

아 코드를 여기다가 옮기는 과정에서 괄호 하나가 빠졌네요.... 제출할 때에는 빠짐 없이 넣어서 제출했었습니다! 흐음.... 대체 문제가 뭘까요....ㅜ.ㅜ

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

문제

문제

출처

ICPC

[백준11724 / C++] 왜 틀렸는지 모르겠습니다. 도와주세요....!

goodluck616 3년 전 0

sonjaewon 3년 전 1

goodluck616 3년 전 0

sonjaewon 3년 전 2

goodluck616 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말