1412 : 일방통행

풀이

단방향과 양방향 간선이 섞여있는 그래프가 주어진다.

양방향 간선들을 모두 단방향 간선으로 바꾸었을 때, 사이클이 있는지 찾는 문제이다.

일단 솔루션부터 이야기하면, 양방향 간선들은 제껴두고 단방향 간선들만으로 사이클을 이루는지 검사하면 된다.

증명은 음… 증명이라고 하긴 뭐하지만

1->2, 1->3, 2->4, 3->4, 1-4, 2-3의 그래프를 가정하자.

단방향 간선들로 위상정렬을 하면, 1 2 3 4가 나올 것이다.

그리고 1-4와 2-3은 위상정렬 순서에 따라 단방향 간선으로 바꾸어주면 된다. (1->4, 2->3)

코드

#include <stdio.h>

int n, vst[101], flag;
char gph[101][101];

void dfs(int u) {
	if (vst[u]) flag = 1;
	if (flag) return;
	vst[u] = 1;
	for (int i = 0; i < n; i++) if (gph[u][i] == 'Y' && gph[i][u] == 'N')
		gph[u][i] = 'N', dfs(i);
	vst[u] = 0;
}

int main() {
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%s", gph[i]);
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (gph[i][j] == 'Y' && gph[j][i] == 'N')
				dfs(i), gph[i][j] = 'N';
			if (flag) {
				puts("NO");
				return 0;
			}
		}
	}
	puts("YES");
	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-04-13 20:50

Read more posts by this author