โถ ์ ํ
- ์ ํฅ ๊ทธ๋ํ์ ์ ์ ๋ค์ ๋ณ์ ๋ฐฉํฅ์ ๊ฑฐ์ค๋ฅด์ง ์๋๋ก ๋์ดํ๋ ๊ฒ์ ์๋ฏธํ๋ค
- ์ ์ ๊ฐ ์์๊ฐ ์๋ค๊ณ ๋ฐ์๋ค์ด๋ฉด ๋๋ค.
- ์์์ ๋ ฌ์ด ์ฑ๋ฆฝํ๋ ค๋ฉด ์ ํฅ๊ทธ๋ํ(indegree, outdegree)๋ฉด์ ์ฌ์ดํด์ด ์์ผ๋ฉด ์๋๋ค.
์์์ ๋ ฌ์ ๊ฐ ์ ์ ์ ์ง์ ์ฐจ์๋ฅผ ์ธ๋ฉด์ ์งํํ๋ค.
์์ํ ๋ ์ง์
์ฐจ์๊ฐ 0์ธ ์ ์ ๋ค์ ์คํ์ ๋ฃ๊ณ ์ ์ ์ ๊บผ๋ด๋ฉด์ ๊ฐ ์ ์๋ ์ธ์ ์ ์ ์ ์ง์
์ฐจ์๋ฅผ 1 ๊ฐ์์ํจ๋ค.
๊ทธ๋ฌ๋ค ์ธ์ ์ ์ ์ ์ง์
์ฐจ์๊ฐ 0์ด ๋๋ฉด ๊ทธ ๋
ธ๋๋ฅผ ์คํ์ ์ง์ด๋ฃ๋๋ค.
โถ ์ ๋ต
์์๋๋ก ๊ทธ๋ ค๋ณด์
์ง์ ์ฐจ์๊ฐ 0์ธ 1,3,4๋ฅผ ๋จผ์ ์คํ์ ๋ฃ๋๋ค(ํ์ฌ๋ ์๊ด์์๊ฒ๊ฐ๋ค)
์ง์ ์ฐจ์๋ฅผ ๊ธฐ์ค์ผ๋ก ์๋ฃ๊ตฌ์กฐ์ ๋ฃ์ด์ผํ๊ธฐ ๋๋ฌธ์ ์ง์ ์ฐจ์๋ง ๊ด๋ฆฌํด์ค ๋ฐฐ์ด์ ํ๋ ์ ์ธํด์ค์ผํ๋ค.
๊ทธ ๋ค์ ์คํ์์ ๋นผ๋ฉด์ ์ธ์ ํ ์ ์ ์ ์ง์ ์ฐจ์๋ฅผ ํ์ธํ๋ค. -> 2, 7, 6์ด๋ค(pop๋๋ฉด์ ์ง์ ์ฐจ์๋ฅผ ํ๋์ฉ ๊ฐ์์ํจ๋ค)
์ ์ 2์ ์ง์ ์ฐจ์๊ฐ 0์ด๋์ผ๋๊น pushํ๊ณ , popํ๋ฉด์ ์ธ์ ํ ์ ์ ์ ์ง์ ์ฐจ์๋ฅผ ํ๋์ฉ ๋ฎ์ถ๋ค.
6, 7์ด ์ง์ ์ฐจ์ 0๋๋ฉด์ pushํ๊ณ , popํ๋ค -> 5๊ฐ ๋ง์ง๋ง์ ๋จ๋๋ค
๋ณด๋ค๋ณด๋ฉด ์ง์ ์ฐจ์๊ฐ ์ ์ผ ์์๊ฒ ๋ถํฐ ๋ฃ์ผ๋ฉด ๋์ง์์๊นํ๋ ์๊ฐ์ด ๋ ๋ค. -> ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํด๋ณด์...
๊ผญ ์ฐ์ ์์ํ๊ฐ ์๋์ด๋ indegree๋ฐฐ์ด๋ก ์ฒ๋ฆฌํ๊ธฐ๋๋ฌธ์ ์๊ด์์ ๊ฒ ๊ฐ๋ค.
# ๋ฌธ์ ํ์ด๋ณด๊ธฐ
https://www.acmicpc.net/problem/1766
์์ฃผ ์์์ ๋ ฌ ๊ทธ ์์ฒด์ธ ๋ฌธ์ ๋ค.
๋ฌธ์ ์์ ์ฐ์ ์กฐ๊ฑด ์ค ์ ์ ๊ฐ์ด ์์ ๊ฒ ์ฐ์ ์ด๋ผ๋ ๋ง์ด ์์ด์ minHeap์ผ๋ก ์ฒ๋ฆฌํ๋ค.
import java.util.*;
import java.io.*;
class Main {
static int n, m;
static int[] indegree;
static List<Integer>[] adj;
static PriorityQueue<Integer> pq;
static StringBuilder sb;
static void topology() {
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0)
pq.add(i);
}
while (!pq.isEmpty()) {
int node = pq.poll();
sb.append(node).append(" ");
for (int nxt : adj[node]) {
indegree[nxt]--;
if (indegree[nxt] == 0)
pq.add(nxt);
}
}
}
public static void main(String[] args) throws Exception {
//System.setIn(new FileInputStream("res/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(st.nextToken());// ๋ฌธ์ ์์ 1~N๊น์ง
m = Integer.parseInt(st.nextToken()); // ๋จผ์ ํธ๋ ๊ฒ ์ข์ ๋ฌธ์ ์ ๋ํ ๊ฐ์
adj = new ArrayList[n + 1]; // ๋ถํฐ N๊น์ง์ ์ธ์ ๋ฆฌ์คํธ
indegree = new int[n + 1];
for (int i = 1; i <= n; i++) {
adj[i] = new ArrayList(); // N๊ฐ์ ์ ์ ์ด๊ธฐํ
}
pq = new PriorityQueue<Integer>((o1, o2) -> {
return o1 - o2;
});
sb = new StringBuilder();
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine(), " ");
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
// to์ ์ ์ ์ง์
์ฐจ์๋ฅผ ๋๋ฆฐ๋ค.
adj[from].add(to);
indegree[to]++;
}
// ์ง์
์ฐจ์๊ฐ 0์ธ์ ๋ค๋ง pq์ ๋ฃ๊ณ ์์ํ๊ธฐ
topology();
System.out.println(sb);
}
}
๋์์ด ๋๋ค๋ฉด ๋๊ธ์ด๋ ๊ณต๊ฐ ๋ฒํผ ํ ๋ฒ์ฉ ๋๋ฅด๊ณ ๊ฐ์ฃผ์ธ์! ๋ก๊ทธ์ธ ์ํด๋ ๋ฉ๋๋ค ^_^
'OJ๐ผ > ์๊ณ ๋ฆฌ์ฆ ์ ํ ์ ๋ฆฌ๐' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์ ๋ ฌ - Comparable<T> ~ compareTo(T o1) (0) | 2024.05.29 |
---|---|
Dynamic Programming์ด ์์ธ DFSโ๏ธ - ๋ด๋ฆฌ๋ง๊ธธ, ์์ฌ์์ด ํ๋ค๐ผ (0) | 2024.04.07 |
Bruteforce๐คฎ - ์์ด, ์กฐํฉ, ๋ถ๋ถ์งํฉ (0) | 2024.03.31 |
์ต๋จ๊ฑฐ๋ฆฌ๐ - ๋ค์ต์คํธ๋ผ Dijkstra (0) | 2024.03.31 |
๋ฐฐ๋ญ ๋ฌธ์ Knapsack๐ - 12865๋ฒ: ํ๋ฒํ ๋ฐฐ๋ญ (2) | 2024.03.25 |