[JAVA][백준 2252] 줄 세우기

사이트명	백준
문제 링크	www.acmicpc.net/problem/2252
주요 알고리즘	위상 정렬, 그래프
사용 언어	Java 자바
설명이 장황합니다.. 도움되는 것만 파악하세요 :-)

1. 문제

2. 입력 / 출력

 

---

3. 풀이

3-1. 생각 노트

맨 처음 단순히 for문을 이용하여 문제를 해결하려 했다.

문제에서 크다/작다로 입력되는 모든 수를 카운팅(크면 +, 작으면 -)하고, 최종적으로 카운팅 된 수 크기대로 출력하는 방식을 생각했다.

	int[][] height = new int[N][2];
	
	for (int i = 0; i < N; i++) {
		height[i][0] = i;
	}
	
	
	for (int i = 0; i < M; i++) {
		int t = sc.nextInt();
		int s = sc.nextInt();
		
		height[t-1][1]++;
		height[s-1][1]--;
	}
	
	
	// 키 순서가 담긴 height[][1] 배열을 정렬하기
	Arrays.sort(height, new Comparator<int[]>() {
		@Override
		public int compare(int[] o1, int[] o2) {
			return o2[1] - o1[1];
		}
	});
	
	
	for (int i = 0; i < N; i++) {
		System.out.print(height[i][0]+1 + " ");
	}

이런 식으로 해결하려 했는데, 곧바로 OUT..

 

그러다, 순서를 정하는 알고리즘인 위상 정렬을 발견해서 이를 토대로 적용했다.

위상 정렬의 핵심은 단방향 그래프를 그린 후, 진입 차수(본인에게 오는 화살표)가 0인 애들을 부터 지우는 방식으로 순서를 정하는 것이다.

따라서, 해야할 일은

 

1. 진입 차수를 기록하는 배열

2. 노드마다 본인이 가르키는 노드를 저장하는 리스트

 

이 두가지를 기록하고, 0일 때마다 노드를 돌면서 지우는 일을 반복하면 된다.

 

3-2. 변수명

변수명	설명
int[] indegree	진입차수(본인에게 들어오는 화살표)를 기록 -> 시작 순서를 정해줌
ArrayList<Integer>[] nodeList	ArrayList로 구성된 배열을 만들어줌. 여기에 이제 노드별로 연결된 노드를 기록함

배열은 세로로, 리스트는 가로로 표시해서 생각했다.

3-3. 코드 보기

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*
 순서를 정하는 위상정렬 알고리즘을 사용한다.
*/

public class BOJ2252_줄세우기 {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();	// 몇 명인지 = 정점 수
		int M = sc.nextInt();	// 비교 횟수 = 간선 수
		
		// 진입차수(자신에게 들어오는 화살표)를 기록
		int[] indegree = new int[N+1]; // 0 인덱스 무시
		
		// 연결 리스트 생성
		ArrayList<Integer>[] nodeList = new ArrayList[N+1];
		
		// 자기가 연결된 녀석들을 가르키는 노드 리스트를 초기화함
		for (int i = 1; i <= N; i++) {
			nodeList[i] = new ArrayList<>();
		}
		
		// =====================================
		// data input
		for (int i = 0; i < M; i++) {
			// from -> to
			int from = sc.nextInt();
			int to = sc.nextInt();
			
			nodeList[from].add(to);
			indegree[to]++;			// 자신에게 들어오는 차수를 기록
		}
		
		// =====================================
		// q를 활용하여 위상정렬을 실시
		Queue<Integer> q = new LinkedList<>();
		// 결과값을 기록하는 변수
		Queue<Integer> result = new LinkedList<>();
		
		// 차수가 0인 녀석들을 먼저 선택
		for (int i = 1; i <= N; i++) {
			if(indegree[i] == 0) {
				q.add(i);
			}
		}
		
		// 위상정렬
		while(!q.isEmpty()) {
			int zero = q.poll();
			result.add(zero);  // 0인 녀석들을 결과에 일단 넣기
			
			for (int i = 0; i < nodeList[zero].size(); i++) {
				// 진입차수가 0인 노드가 가르키는 녀석들을 순차적으로 탐색
				// 가르키는 녀석들의 진입차수를 지우기
				int current = nodeList[zero].get(i);
				indegree[current]--;
				
				if(indegree[current] == 0) {
					q.add(current);
				}
			}
		}
		
		for (Integer i : result) {
			System.out.print(i + " ");
		}
		
	}

}

 

3-4. 마무리

진입 차수를 따로 기록받아, 이것이 0이 되는 노드를 먼저 찾으며 순서를 결정하는 알고리즘!

 

 

 

 

 

#알고리즘풀이 #백준