[백준] 2252번 줄 세우기 문제 풀이(Java) - 세무민의 코딩일기

오늘 포스팅할 문제는 줄세우기 문제입니다.

---

1. 문제 내용 

---

2. 입출력

---

3. 문제 풀이 

우선 이번 문제는 그래프를 이용해서 푸는 문제이며 위상정렬을 이용한 문제이다.

위상정렬이라고 한다면 순서가 정해진 정렬이지만 싸이클이 없는 즉 단방향(사이클 발생 X) 그래프를 말한다.

문제를 좀 더 확인해보자.

N명의 학생들의 키를 순서대로 줄을 세울려고 하는데 두 학생의 키를 비교하여 정렬을 한다고 가정한다. 

첫번째 예제를 입력했을 때 줄을 세워진 방법이다.

1번의 친구와 3번의 친구를 비교하고 2번의 친구와 3번의 친구를 비교한다고 가정하면 

3번의 친구는 1번과 2번의 친구를 비교한 상태 즉 2명과 비교했고 

1번과 2번은 3번과 비교한 것을 제외하고 비교 대상이 없다. 즉 1과 2와 진입차수가 없다는 것을 확인할 수 있다. 

그렇다면 코드로 이것을 표현한다면 말 그대로 진입차수가 0인 친구들부터 줄을 세우게 된다면 결국 

키를 자연스럽게 순서대로 정렬할 수 있다. 

여기서 진입차수가 0인 친구들은 결국에 서로 비교하지 않았기 때문에 서로의 순서는 크게 의미가 없다. 

---

4. 코드

/**
 * [위상정렬]
 * 그래프의 노드가 거스르지 않고 연결되어있는 그래프가 되도록 정렬하는 방식을 말함 
 * DAG에만 적용이 가능한 정렬방식
 * 요점 : 순서가 정해진 정렬을 말함(사이클이 발생하면 안됨)
 * 방식 : Stack / Queue 2가지를 사용 가능 
 * 주로 사용하는 방식 : Queue 방식
 * 				-> 2차원 배열을 사용 
 * 
 * ex) 연결된 그래프가 3 - 1, 3 - 2 라고 가정하면
 * 3은 1과 2가 연결되어 있기 때문에 2개의 진입차수(간선의 개수)를 가지고
 * 1과 2는 0개의 진입차수를 가진다. 
 * 그렇기 때문에 위상정렬에 따르면 진입차수가 0인 친구들부터 나열하고 진입차수가 0이상인 경우 0으로 하나씩 빼주면서 계산하면 된다.
 * 
 * >> 번외
 * scanner보다 입출력 속도가 빠른 BufferedReader와 BufferedWriter로 입출력을 받는다. 
 * StringTokenizer를 이용하여 문자열의 공백을 체크
 * 
 * >> 변수 
 * degree : 진입차수를 위한 정수배열 
 * sortList : 입력받은 노드들의 연결관계를 나타내기 위한 정수 ArrayList
 * lNum과 rNum : n과 m값
 * 
 * */

// 위상정렬에서 DFS 방식보단 Qeueu를 쓰는 것이 효율적 
public class backjoon_2252 {
	static int n;
	static int m;

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st;
		st = new StringTokenizer(reader.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		int[] degree = new int[n];
		ArrayList<ArrayList<Integer>> sortList = new ArrayList<>();
		
		for(int i = 0; i < n; i++) {
			sortList.add(new ArrayList<Integer>()); 
		}
		
		// 연결하는 값에 간선들을 sortList와 degree에 표시해준다. 
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(reader.readLine());
			int lNum = Integer.parseInt(st.nextToken());
			int rNum = Integer.parseInt(st.nextToken());
			sortList.get(lNum-1).add(rNum-1);
			degree[rNum-1]++;
		}

	
		Queue<Integer> queue = new LinkedList<Integer>();
		Queue<Integer> result = new LinkedList<Integer>();
		
		
		// 자신을 가르키고 있는것이 없다면 진입차수가 0이기 때문에 queue에 추가한다.
		for(int i = 0; i < n; i++) {
			if(degree[i] == 0) {
				queue.add(i);
			}
		}
		
		int current;
		while(!queue.isEmpty()) {
			// 하나씩 결과 큐에 값을 넣으면서 연결된 노드들을 탐방하고 진입차수가 0이되면 동일하게 Queue로 들어온다. 
			current = queue.poll();
			result.add(current);
			
			for(int i : sortList.get(current)) {
				degree[i]--;
				
				if(degree[i]==0) {
					queue.add(i);
				}
				
			}
			
		}
	
		while(!result.isEmpty()) {
			writer.write((result.poll() + 1) + " ");
		}
		
		writer.flush();
		writer.close();
	}
}

위와같이 구성했다. 

sortList는 말 그대로 연결된 ArrayList와 degree인 정수배열을 생성하여

degree에서는 진입차수의 개수를 0인지 체크하고 sortList에서는 연결된 친구들을 Queue에 넣어서 확인하고

연결된 친구들을 확인했다면 result에 넣어서 나열시켜주면 끝입니다.

---

5. 결과

이번 포스팅에서는 알고리즘 문제를 풀어봤습니다.

항상 직장인이라는 변명속에서 항상 공부를 잘 안했는데 알고리즘 문제를 풀면서 좀 더 자극을 받을 수 있었습니다.

다음에도 더 좋은 정보로 찾아오겠습니다.