글 읽기 - 반례좀 찾아주세요 알고리즘이 잘못된걸까요?

soloranker66 4년 전 0

양방향 간선은 전부 없다고 취급하고

위상정렬 알고리즘을 통해 싸이클만 남겨두게 했습니다.

싸이클이 남겨졌단소리는 위상정렬이 끝났음에도 indegree가 1이상인 간선이 존재한다는 뜻이랑 같은걸로 파악했는데 알고리즘의 문제일까요

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;

struct _node {
	int indegree;
	vector<int> edge;
}node[101] = { 0, };

queue <int> q;

char map[101][101];

int main() {
	int size;
	scanf("%d", &size);
	for (int i = 0; i < size; i++)
		scanf(" %s", map[i]);
	for(int i=0;i<size;i++)
		for (int n = 0; n < size; n++) {
			if (map[i][n] != map[n][i] && map[i][n] == 'Y') { // 단방향 간선만 취급
				node[i].edge.push_back(n);
				node[n].indegree++;
			}	
			if (i == n && map[i][n] == 'Y') { // 자기 자신으로 돌아오는 루프는 불가능
				printf("NO");
				return 0;
			}
		}
	for (int i = 0; i < size; i++)
		if (node[i].indegree == 0) // indegree가 0인 간선만 추가
			q.push(i);
	while (!q.empty()) { // 위상정렬
		int p = q.front();
		q.pop();
		for (int i = 0; i < node[i].edge.size(); i++) {
			int next = node[p].edge[i];
			node[next].indegree--;
			if (node[next].indegree == 0)
				q.push(next);
		}			
	}
	for (int i = 0; i < size; i++) // 위상정렬이 끝났음에도 indegree가 1이상이면 불가능
		if (node[i].indegree > 0) {
			printf("NO");
			return 0;
		}
	printf("YES");
}

soloranker66 4년 전 0

멍청했네요.. 39번째 줄 for문에 node[p]로 했어야했는데..

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

문제

문제

출처

ICPC

반례좀 찾아주세요 알고리즘이 잘못된걸까요?

soloranker66 4년 전 0

soloranker66 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말