글 읽기 - 11403번 반례찾습니다!!

johnbae57 6년 전 0

알고리즘 입문생입니다!!!

원래 밑의 코드와 비슷하게 알고리즘 짰었는데
자꾸 런타임에러가 나서 처음부터 다시 짜봤습니다.
그랬더니 런타임에러는 나지않고 채점에서 79% 까지 올라가다가 틀렸다고 나오네요ㅠ

고수님들 반례가 있을까요??
질문게시판에 나와있는 다른 반례들은 다 해봤는데 정상출력 됩니다.

3일동안 이 한문제가지고 끙끙대는중입니다 ㅠ
부탁드립니다!

#include <stdio.h>

int n;
int vector_matrix[110][110];

int flag[110];  //방문 안했으면 0 , 했으면 1

int stack[110]; // 지나온 경로 저장
int top = -1;

int top2 = -1; //stack2 의 peak index 값;
int stack2[110]; // 길 못찾았을시 flag 비워주기위해

// 길있으면 1, 없으면 0 반환
int DFS(int from, int to) {
	flag[from] = 1;
	// 경로 저장
	stack[++top] = from;
	stack2[++top2] = from;

	// 길 찾으면
	if (vector_matrix[from][to] == 1) {
		// flag 비워주고 경로들 모두 1로바꿔주기
		for (int j = top; j > -1; j--) {
			vector_matrix[stack[j]][to] = 1;
			flag[stack[j]] = 0;
		}
		top = -1;
		return 1;
	}
	
	else {
		// 다른길 있나 탐색
		for (int i = 1; i <= n; i++) {
			if (from == i) continue;
			
			//다른길 i 있으면
			if (vector_matrix[from][i] == 1 && flag[i] == 0) {
				int a;
				// from - > i
				a = DFS(i, to);
				if (a == 1) {
					return 1;
				}
			}


		}
	}
	top--;
	return 0;
}


int main() {
	scanf("%d", &n);
	int a;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &vector_matrix[i][j]);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			a = DFS(i, j);
			
			// 길 못찾았을때 flag 비워주기
			if (a == 0) {
				for (int k = top2; k > -1; k--) {
					flag[stack2[k]] = 0;
				}
			}
			top2 = top -1;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			printf("%d ", vector_matrix[i][j]);
		}
		printf("\n");
	}
}

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

문제

문제

출처

ICPC

11403번 반례찾습니다!!

johnbae57 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말