๋ฏผ์ค๋ 1๋ฒ๋ถํฐ N๋ฒ๊น์ง ์ด N๊ฐ์ ๋ฌธ์ ๋ก ๋์ด ์๋ ๋ฌธ์ ์ง์ ํ๋ ค๊ณ ํ๋ค. ๋ฌธ์ ๋ ๋์ด๋ ์์๋ก ์ถ์ ๋์ด ์๋ค. ์ฆ 1๋ฒ ๋ฌธ์ ๊ฐ ๊ฐ์ฅ ์ฌ์ด ๋ฌธ์ ์ด๊ณ N๋ฒ ๋ฌธ์ ๊ฐ ๊ฐ์ฅ ์ด๋ ค์ด ๋ฌธ์ ๊ฐ ๋๋ค.
์ด๋ค ๋ฌธ์ ๋ถํฐ ํ๊น ๊ณ ๋ฏผํ๋ฉด์ ๋ฌธ์ ๋ฅผ ํ์ด๋ณด๋ ๋ฏผ์ค๋, ๋ช๋ช ๋ฌธ์ ๋ค ์ฌ์ด์๋ '๋จผ์ ํธ๋ ๊ฒ์ด ์ข์ ๋ฌธ์ '๊ฐ ์๋ค๋ ๊ฒ์ ์๊ฒ ๋์๋ค. ์๋ฅผ ๋ค์ด 1๋ฒ ๋ฌธ์ ๋ฅผ ํ๊ณ ๋๋ฉด 4๋ฒ ๋ฌธ์ ๊ฐ ์ฝ๊ฒ ํ๋ฆฐ๋ค๊ฑฐ๋ ํ๋ ์์ด๋ค. ๋ฏผ์ค๋ ๋ค์์ ์ธ ๊ฐ์ง ์กฐ๊ฑด์ ๋ฐ๋ผ ๋ฌธ์ ๋ฅผ ํ ์์๋ฅผ ์ ํ๊ธฐ๋ก ํ์๋ค.
1. N๊ฐ์ ๋ฌธ์ ๋ ๋ชจ๋ ํ์ด์ผ ํ๋ค.
2. ๋จผ์ ํธ๋ ๊ฒ์ด ์ข์ ๋ฌธ์ ๊ฐ ์๋ ๋ฌธ์ ๋, ๋จผ์ ํธ๋ ๊ฒ์ด ์ข์ ๋ฌธ์ ๋ฅผ ๋ฐ๋์ ๋จผ์ ํ์ด์ผ ํ๋ค.
3. ๊ฐ๋ฅํ๋ฉด ์ฌ์ด ๋ฌธ์ ๋ถํฐ ํ์ด์ผ ํ๋ค.
์๋ฅผ ๋ค์ด์ ๋ค ๊ฐ์ ๋ฌธ์ ๊ฐ ์๋ค๊ณ ํ์. 4๋ฒ ๋ฌธ์ ๋ 2๋ฒ ๋ฌธ์ ๋ณด๋ค ๋จผ์ ํธ๋ ๊ฒ์ด ์ข๊ณ , 3๋ฒ ๋ฌธ์ ๋ 1๋ฒ ๋ฌธ์ ๋ณด๋ค ๋จผ์ ํธ๋ ๊ฒ์ด ์ข๋ค๊ณ ํ์. ๋ง์ผ 4-3-2-1์ ์์๋ก ๋ฌธ์ ๋ฅผ ํ๊ฒ ๋๋ฉด ์กฐ๊ฑด 1๊ณผ ์กฐ๊ฑด 2๋ฅผ ๋ง์กฑํ๋ค. ํ์ง๋ง ์กฐ๊ฑด 3์ ๋ง์กฑํ์ง ์๋๋ค. 4๋ณด๋ค 3์ ์ถฉ๋ถํ ๋จผ์ ํ ์ ์๊ธฐ ๋๋ฌธ์ด๋ค. ๋ฐ๋ผ์ ์กฐ๊ฑด 3์ ๋ง์กฑํ๋ ๋ฌธ์ ๋ฅผ ํ ์์๋ 3-1-4-2๊ฐ ๋๋ค.
๋ฌธ์ ์ ๊ฐ์์ ๋จผ์ ํธ๋ ๊ฒ์ด ์ข์ ๋ฌธ์ ์ ๋ํ ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋, ์ฃผ์ด์ง ์กฐ๊ฑด์ ๋ง์กฑํ๋ฉด์ ๋ฏผ์ค๊ฐ ํ ๋ฌธ์ ์ ์์๋ฅผ ๊ฒฐ์ ํด ์ฃผ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋ฌธ์ ์ ์ N(1 โค N โค 32,000)๊ณผ ๋จผ์ ํธ๋ ๊ฒ์ด ์ข์ ๋ฌธ์ ์ ๋ํ ์ ๋ณด์ ๊ฐ์ M(1ย โค M โค 100,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์ ๊ฑธ์ณ ๋ ์ ์์ ์์์ A,B๊ฐ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. ์ด๋ A๋ฒ ๋ฌธ์ ๋ B๋ฒ ๋ฌธ์ ๋ณด๋ค ๋จผ์ ํธ๋ ๊ฒ์ด ์ข๋ค๋ ์๋ฏธ์ด๋ค.
ํญ์ ๋ฌธ์ ๋ฅผ ๋ชจ๋ ํ ์ ์๋ ๊ฒฝ์ฐ๋ง ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๋ฌธ์ ๋ฒํธ๋ฅผ ๋ํ๋ด๋ 1 ์ด์ N ์ดํ์ ์ ์๋ค์ ๋ฏผ์ค๊ฐ ํ์ด์ผ ํ๋ ์์๋๋ก ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ถ๋ ฅํ๋ค.
๐ก ์์์ ๋ ฌ + ์ฐ์ ์์ ํ
๐ก ์ ์๋ฌธ์ ๋ฅผ ํผ ํ, ํ ์ ์๋ ๋ฌธ์ ๋ฅผ list์ ์ ์ฅํจ / ์ง์
์ฐจ์ ๋๋ ค์ค
๐ก ์ง์
์ฐจ์๊ฐ 0์ธ ์๋ฅผ ์ฐ์ ์์ ํ์ ๋ฃ์
๐ก ํ์์ ํ๋๋ฅผ ๋นผ๊ณ ์ดํ์ ํ ๋ฌธ์ ๋ฅผ list์์ ๊ฐ์ ธ์์ ์ง์
์ฐจ์ ์ค์ฌ์ค
๐ก ์ง์
์ฐจ์๊ฐ 0์ด ๋๋ฉด ์ฐ์ ์์ ํ์ ๋ฃ์
for(int i=0; i<m; i++) {
s = br.readLine().split(" ");
int a = Integer.parseInt(s[0]);
int b = Integer.parseInt(s[1]);
list[a].add(b);
indegree[b]++;
}
for(int i=1; i<n+1; i++) {
if(indegree[i] == 0)
pq.add(i);
}
int cur = pq.poll();
for(int con : list[cur]) {
...
}
indegree[con]--;
if(indegree[con] == 0) {
pq.add(con);
}
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.PriorityQueue;
public class BOJ_1766 {
static int[] indegree;
static int n, m;
static ArrayList<Integer>[] list;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
indegree = new int[n+1];
list = new ArrayList[n+1];
for(int i=1; i<n+1; i++) {
list[i] = new ArrayList<Integer>();
}
for(int i=0; i<m; i++) {
s = br.readLine().split(" ");
int a = Integer.parseInt(s[0]);
int b = Integer.parseInt(s[1]);
list[a].add(b);
indegree[b]++;
}
String str = sort();
bw.write(str);
bw.flush();
bw.close();
}
static String sort() {
PriorityQueue<Integer> pq = new PriorityQueue<>();
StringBuilder sb = new StringBuilder();
for(int i=1; i<n+1; i++) {
if(indegree[i] == 0)
pq.add(i);
}
while(!pq.isEmpty()) {
int cur = pq.poll();
for(int con : list[cur]) {
indegree[con]--;
if(indegree[con] == 0) {
pq.add(con);
}
}
sb.append(Integer.toString(cur));
sb.append(" ");
}
return sb.toString();
}
}
์ฑ๊ณตโจ