문제 - https://www.acmicpc.net/problem/3665
3665번: 최종 순위
올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에
www.acmicpc.net
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int N, M;
static int[] order;
static class Node{
int id, oriOrder, inDegree;
Set<Integer> outDirect;
public Node(int id, int ord){
this.id = id;
this.oriOrder = ord;
this.inDegree = ord;
this.outDirect = new HashSet<>();
}
}
static HashMap<Integer, Node> nodes;
public static void main(String[] args) throws Exception {
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
N = Integer.parseInt(br.readLine());
order = new int[N];
nodes = new HashMap<>();
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int id = Integer.parseInt(st.nextToken());
order[j] = id;
nodes.put(id, new Node(id, j));
for (int k = 0; k < j; k++) {
nodes.get(order[k]).outDirect.add(id);
}
}
M = Integer.parseInt(br.readLine());
for (int j = 0; j < M; j++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
swap(nodes.get(a), nodes.get(b));
}
sb.append(sort()+"\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
static void swap(Node A, Node B){
if (!A.outDirect.contains(B.id)){
Node tmp = A;
A = B;
B = tmp;
}
A.outDirect.remove(B.id);
A.inDegree++;
B.outDirect.add(A.id);
B.inDegree--;
}
static String sort(){
Queue<Node> Q = new ArrayDeque<>();
for (Map.Entry<Integer, Node> E : nodes.entrySet()) {
if (E.getValue().inDegree==0){
if (Q.size()==1) return "?";
Q.add(E.getValue());
}
}
StringBuilder order = new StringBuilder();
for (int i = 0; i < N; i++) {
if (Q.isEmpty()) return "IMPOSSIBLE";
Node cur = Q.poll();
order.append(cur.id+" ");
for (int next : cur.outDirect){
nodes.get(next).inDegree--;
if (nodes.get(next).inDegree == 0) Q.add(nodes.get(next));
}
}
return order.toString();
}
}위상정렬 문제라는건 파악했지만, 정말 로직을 생각하고 구현하는데 너무너무 어려웠다...
위상정렬에 대한 부분이 많이 약한것같다! 연습하자!
'공부 > algorithm' 카테고리의 다른 글
| BOJ 치즈(2636) - Java (0) | 2021.11.16 |
|---|---|
| BOJ 연구소 2(17141) - Java (0) | 2021.11.16 |
| BOJ 회의실 배정(1931) - Java (0) | 2021.10.25 |
| BOJ 쉬운 계단 수(10844) - Java (0) | 2021.10.23 |
| BOJ 내리막 길(1520) - Java (0) | 2021.10.20 |