[BOJ] 백준 2252 - 줄 세우기 풀이

1. 문제

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

2. 풀이

• 문제에서 A 다음에 B가 나올 경우 A가 B보다 앞에 있어야 하므로 인접 리스트로 생각한다면 A 노드 다음에 B노드가 연결되어 있다고 생각할 수 있다.
• 그리고 1 3 이 주어졌을 때 3 1이 또 주어지는 경우는 없으므로 한 방향으로만 흐른다.
• 노드 다음 특정 노드를 연결하고 이를 순서대로 출력해야 하므로 위상 정렬을 생각할 수 있다.
• 주요 자료구조
  • List<Integer>[] inList : 인접리스트
  • int[] inDegree : 진입 차수 배열
  • List<Integer> numList : 사이클이 발생하지 않는 노드가 들어있는 리스트
• 주어진 입력을 받아 인접 리스트를 구성하고 lineUpTopologicalSort()를 실행한다.
  • 진입 차수가 0인 노드를 Queue에 넣는다.
  • while 반복문을 돌면서 다음과 같은 로직을 수행한다.
    1. Queue에서 poll을 한다.
    2. Queue에 들어갔다는 것은 사이클이 만들어지지 않았다는 의미이므로 줄을 세울 수 있다. 따라서 numList에 노드를 추가한다.
    3. poll한 노드와 인접한 노드를 탐색하면서 진입 차수가 0인 노드를 찾고 이를 Queue에 넣어준다.
• 마지막으로 numList에 들어 있는 노드를 순서대로 출력만 해주면 된다.
  
  

3. 소스 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static List<Integer>[] inList;
	static int[] inDegree;
	static List<Integer> numList;
	
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    N = Integer.parseInt(st.nextToken());
	    M = Integer.parseInt(st.nextToken());
	    
	    // 인접리스트 초기화
	    inList = new ArrayList[N + 1];
	    for (int i = 1; i <= N; i++) {
	    	inList[i] = new ArrayList<>();
	    }
	    
	    // 진입차수 배열
	    inDegree = new int[N + 1];
	    
	    // 인접 리스트 연결
	    for (int i = 0; i < M; i++) {
	    	st = new StringTokenizer(br.readLine());
	    	
	    	int from = Integer.parseInt(st.nextToken());
	    	int to = Integer.parseInt(st.nextToken());
	    	
	    	inList[from].add(to);
	    	inDegree[to] += 1;
	    }
	    
	    numList = new ArrayList<>();
	    
	    // 위상 정렬
	    lineUpTopologicalSort();
	    
	    // 출력
	    for (int i = 0; i < numList.size(); i++) {
	    	bw.write(numList.get(i) + " ");
	    }
	    bw.close();
	    br.close();
	}

	// 위상 정렬 함수
	private static void lineUpTopologicalSort() {
		Queue<Integer> q = new ArrayDeque<Integer>();
		
		// 진입 차수가 0인 노드를 넣기
		for (int i = 1; i < N + 1; i++) {
			if (inDegree[i] == 0) {
				q.add(i);
			}
		}
		
		while (!q.isEmpty()) {
			int t = q.poll();
			numList.add(t);
			
			for (int i = 0; i < inList[t].size(); i++) {
				if (inList[t].get(i) != null && --inDegree[inList[t].get(i)] == 0) {
					q.add(inList[t].get(i));
				}
			}
		}
	}
}

 

4. 점수

85 / 100