위상정렬

[WonYong-Jang]

위상정렬 ( 그래프 정렬 )

• 위상정렬이 가능하려면 DAG 그래프 여야함!

• Directed Acyclic Graph의 약자로 방향성이 있고, 사이클이 없는 그래프

• 위상 정렬이 필요한 경우는 그래프에서 반드시 자신보다 선행되어야 할 일을 다 끝내야만 작업에 들어갈수 있는 조건이 주어질 때

• 진입차수가 0이라는 것은 자신보다 선행되어야 할 노드 일이 다끝나서 이제 진행해도 된다는 뜻!

• 예) 대학교 수업 듣는 순서, 스타 건물 짓는 순서

위상정렬 구현 시나리오

1. 인접 리스트 형식의 그래프 생성 한 뒤, 각 노드별로 진입차수를 기록
2. indegree ( 진입차수 ) 0인 노드들을 탐색 후 ==> 큐 삽입
3. 입접리스트 이용하여 이동하면서 방문한 노드는 진입 차수 -1 변경
4. 큐를 이용하여 연결된 노드들을 방문하는데 방문할때마다 degree를 하나씩 낮춰주며 degree 가 0이 되는 노드들을 큐에 넣고 계속하여 탐색

예 ) 가수 출연 순서

• 1 4 3
• 6 2 5 4
• 2 3
  == > 6 2 1 5 4 3 또는 1 6 2 5 4 3

참고 링크 : https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=220800013823&proxyReferer=https%3A%2F%2Fwww.google.com%2F

사이클 확인

• N개의 노드를 한번씩 돌기도 전에 큐가 비어 버린다면 위상 정렬 불가능!!!!!!!
• 사이클이 생겼다면 싸이클에 속하는 정점들 중엔 indegree가 0인 정점 한개도 없음
  즉 N개의 노드들을 한번씩 다 도는지 확인 하던지 indegree 의 값이 전부 0인지 확인 하는 방법

		
		for(int i=1; i<= N; i++) // inddegree 0 인 노드 큐에 삽입
		{
			if(degree[i] == 0) que.add(i); 
		}
		solve();
		if(!flag) // 사이클 발생 안한 경우 
		{
			for(int i=0; i< temp.size(); i++)
			{
				System.out.println(temp.get(i));
			}
		}
		
	}
	public static void solve()
	{
		for(int i=0; i< N; i++)
		{
			if(que.isEmpty()) // N 번 돌지 못하고 끝이 나는 것은 사이클 발생 
			{
				System.out.println(0);
				flag = true;
				return;
			}
			
			int n = que.poll();
			
			temp.add(n);
			
			for(int next : adj.get(n))
			{
				degree[next]--;         //연결된 노드 indegree --
				if(degree[next] == 0) // indegree 0 인 노드는 큐에 삽입 
				{
					que.add(next);
				}
			}
		}
	}

• 백준 2252 줄세우기 , 1766 문제집 , 2623 음악프로그램, 1516 게임 개발, 1005 acm craft , 9470 strahler 순서

[WonYong-Jang]

위상정렬 응용 문제

문제 : 색칠 공부

https://koitp.org/problem/COCI_2014C2_PALETA/read/