문제 설명
N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.
일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.
학생들의 번호는 1번부터 N번이다.
출력
첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.
내 답
1차 시도 (오답)
문제를 계속 째려보다 보니 위상정렬 알고리즘이 생각났다.
주어지는 입력에서 키를 비교한 입력값 각각을 간선이라고 생각하고,
앞에 오는 숫자가 시작노드, 뒤에 오는 숫자가 종점 노드가 되는 방향 그래프를 그려
나를 향하는 노드가 없는 노드부터 큐에 담아 순서대로 출력하는 그림을 그린 후 코드를 작성했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[][] adjArr;
static boolean[] visited;
static StringBuilder sb;
public static void main(String[] args) throws IOException {
init(); // 변수 선언 및 초기화 메서드
wisangSort(); // 위상정렬
print(); // 출력 메서드
}
// 변수 선언 및 초기화 메서드
static void init() throws IOException {
sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 학생 수
M = Integer.parseInt(st.nextToken()); // 학생 수
adjArr = new int[N + 1][N + 1]; // 인접행렬
for (int r = 0; r < M; r++) {
st = new StringTokenizer(br.readLine());
adjArr[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 1;
} // 인접행렬 작성
visited = new boolean[N + 1]; // 방문배열
}
// 위상정렬 수행 메서드
private static void wisangSort() {
Queue<Integer> q = new LinkedList<>();
// 자기 자신을 향하는 노드가 없는 시작지점 노드를 큐에 삽입
out: for (int e = 1; e <= N; e++) {
for (int s = 1; s <= N; s++) {
if (adjArr[s][e] > 0)
continue out;
}
q.add(e);
visited[e] = true;
}
while (!q.isEmpty()) {
int curr = q.poll(); // 큐에서 뽑기
sb.append(curr).append(' '); // 스트링빌더에 추가
// 인접행렬을 뒤져 아직 방문 안했으면서 인접한 노드를 큐에 삽입
for (int i=1; i<=N; i++) {
if (adjArr[curr][i] > 0 && !visited[i]) {
q.add(i);
visited[i] = true;
}
}
}
}
// 출력 메서드
private static void print() {
System.out.println(sb);
}
}
결과는 메모리 초과.
원인으로 의심되는 것들은 크게 2가지였다.
1. 방문배열을 추가적으로 선언하여 불필요한 메모리 사용
2. 인접리스트 대신 인접 행렬을 사용하여 불필요한 메모리 사용
하지만 둘 모두 수정해보아도 메모리 초과는 여전했다.
2차 시도 (정답)
결국 원인은 위상정렬을 구현하는 과정의 문제였다.
위상정렬 알고리즘을 생각한 것은 잘했지만, 구체적인 구현 방법이 생각나지 않아
내가 머리속에서 굴린 알고리즘으로만 구현했더니 통과가 안되었다.
결국 위상정렬 알고리즘을 다시 찾아보고 나서야 정답을 맞출 수 있었다.
package boj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N, M;
static List<Integer>[] adjList;
static int[] inDegree;
static StringBuilder sb;
public static void main(String[] args) throws IOException {
init(); // 변수 선언 및 초기화 메서드
wisangSort(); // 위상정렬
print(); // 출력 메서드
}
// 변수 선언 및 초기화 메서드
static void init() throws IOException {
sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 학생 수
M = Integer.parseInt(st.nextToken()); // 비교 횟수
adjList = new ArrayList[N + 1]; // 인접 리스트
inDegree = new int[N + 1]; // 진입 차수
for (int i = 1; i <= N; i++) {
adjList[i] = new ArrayList<>();
}
for (int r = 0; r < M; r++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
adjList[u].add(v); // u -> v 간선 추가
inDegree[v]++; // v의 진입 차수 증가
}
}
// 위상정렬 수행 메서드
private static void wisangSort() {
Queue<Integer> q = new LinkedList<>();
// 진입 차수가 0인 노드를 큐에 삽입
for (int i = 1; i <= N; i++) {
if (inDegree[i] == 0) {
q.add(i);
}
}
while (!q.isEmpty()) {
int curr = q.poll(); // 큐에서 뽑기
sb.append(curr).append(' '); // 스트링빌더에 추가
// curr와 인접한 노드들에 대해 진입 차수를 감소시키고 0이 되면 큐에 추가
for (int neighbor : adjList[curr]) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
q.add(neighbor);
}
}
}
}
// 출력 메서드
private static void print() {
System.out.println(sb);
}
}
결론은
방문배열을 사용하는 것이 아니라,
진입차수 배열을 생성하여
큐에서 꺼낸 노드와 인접한 노드들과의 간선을 1개씩 제거하며 진입차수를 떨어트리고,
진입차수가 0인 것들을 큐에 담는 과정이 필요했다...
다시한번 위상정렬 알고리즘을 공부할 수 있는 기회가 되었다.
다음에는 진입차수 배열을 사용하는 것을 잊지 말아야지!