[백준] 2252번 '줄 세우기' - Java

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

2252번: 줄 세우기

---

문제

---

코드

import java.io.*;
import java.util.*;

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		ArrayList<Integer>[] graph = new ArrayList[n + 1];
		int[] indegree = new int[n + 1];
		
		for(int i = 1 ; i <= n ; i++) {
			graph[i] = new ArrayList<>();
		}
		
		for(int i = 0 ; i < m ; i++) {
			st = new StringTokenizer(bf.readLine());
			int s = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
            // b -> s 방향의 그래프를 만듦
			graph[b].add(s);
            
            // s 로 진입하므로 s의 진입차수를 더해줌
			indegree[s]++;
		}
		
		Queue<Integer> q = new LinkedList<>();
		for(int i = 1 ; i <= n ; i++) {
        	// 진입차수가 0인 노드부터 시작하기 위한 초기 세팅
			if(indegree[i] == 0) {
				q.offer(i);
			}
		}
        
        // 큐에서 나오는대로 값을 저장해놓을 스택
        // 뒤에 들어가야 하는 값이 가장 나중에 출력되어야 하므로 출력 편의상 스택을 이용함
		Stack<Integer> s = new Stack<>();
		while(!q.isEmpty()) {
			int front = q.poll();
			s.push(front);
            // front가 가리키는 애들을 순서대로 탐색함
			for(int next : graph[front]) {
            	// 가리키는 애의 진입차수 삭제 (어차피 front해당 숫자는 poll하기 때문)
				indegree[next] --;
                // 진입차수가 0이라면 큐에 offer
				if(indegree[next] == 0) {
					q.offer(next);
				}
			}
		}
		
        // 스택에서 pop 하여 순서대로 출력
		while(!s.isEmpty()) {
			bw.write(s.pop() + " ");
		}
		
		bf.close();
		bw.flush();
		bw.close();
	}
}

 

생각을 해보니까 처음부터 큐를 사용하지 않고 ArrayList를 이용하여 포인터처럼 가리키는 방법을 사용해서 공간적인 낭비를 줄일 수 있지 않을까 라는 생각을 해봤습니다.

 

밑에는 그 코드입니다. 확실히 메모리에서 약간은 낭비가 줄었네요. 시간도 줄었습니다.

import java.io.*;
import java.util.*;

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		ArrayList<Integer>[] graph = new ArrayList[n + 1];
		int[] indegree = new int[n + 1];
		
		for(int i = 1 ; i <= n ; i++) {
			graph[i] = new ArrayList<>();
		}
		
		for(int i = 0 ; i < m ; i++) {
			st = new StringTokenizer(bf.readLine());
			int s = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			graph[b].add(s);
			indegree[s]++;
		}
		
		ArrayList<Integer> arr = new ArrayList<>();
		for(int i = 1 ; i <= n ; i++) {
			if(indegree[i] == 0) {
				arr.add(i);
			}
		}
		
		int start = 0;
		while(start < n) {
			int front = arr.get(start);
			for(int next : graph[front]) {
				indegree[next] --;
				if(indegree[next] == 0) {
					arr.add(next);
				}
			}
			start ++;
		}
		
		for(int i = n - 1 ; i >= 0 ; i--) {
			bw.write(arr.get(i) + " ");
		}
		
		bf.close();
		bw.flush();
		bw.close();
	}
}

 

---

https://cuckoobird.tistory.com/127

[백준] 1516번 '게임 개발' - Java

전에 위상정렬을 푼 문제를 참고했습니다. 이번에 확실히 이해가 가네요.