문제
https://www.acmicpc.net/problem/3665
풀이
2가지 방법으로 풀이 가능하다.
(1) indegree 가 저장된 2차원 배열을 Sort하는 방법
-> 이 방법이 가능한 이유는, indegree가 순위 정보를 나타내기 때문에 무조건 1씩 증가하는 형태를 보일 수 밖에 없다.
indegree 값이 1씩 증가하지 않는 경우, 순위 정보가 잘못된 것!!
(2) queue 를 이용한 위상정렬
(1) indegree 가 저장된 2차원 배열을 Sort하는 방법
import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; public class BOJ3665_2_by_sort { final static int team = 0; final static int degreeVal = 1;
public static void main(String[] args) throws Exception{ System.setIn(new FileInputStream("src/input.txt")); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st;
int T = Integer.parseInt(br.readLine()); for(int t=1; t<=T; t++) { int N = Integer.parseInt(br.readLine()); int rank[] = new int[N+1];
st = new StringTokenizer(br.readLine()); for(int i=1; i<=N; i++) { rank[i] = Integer.parseInt(st.nextToken()); }
// indegree & map 생성하기 int degreeMap[][] = new int[N+1][2]; boolean map[][] = new boolean[N+1][N+1];
for(int i=1; i<=N; i++) { int teamNum = rank[i];
degreeMap[teamNum][team] = teamNum; degreeMap[teamNum][degreeVal] = i-1;
for(int j=1; j<i; j++) { map[teamNum][rank[j]] = true; } }
// 순위 바꾸기 int K = Integer.parseInt(br.readLine()); for(int i=1; i<=K; i++) { st = new StringTokenizer(br.readLine()); int team1 = Integer.parseInt(st.nextToken()); int team2 = Integer.parseInt(st.nextToken());
if(map[team1][team2]) { degreeMap[team1][degreeVal]--; degreeMap[team2][degreeVal]++; }else { degreeMap[team1][degreeVal]++; degreeMap[team2][degreeVal]--; }
map[team1][team2] = !map[team1][team2]; map[team2][team1] = !map[team2][team1]; }
// Indegree 값으로 Sort degreeMap[0][degreeVal] = -1; // 0은 사용하지 않는 Index 이므로 Sort에 영향받지 않도록 // 만일 indegree 값이 0보다 작은 값이 생겨서 sort가 어그러지더라도 결국 출력시에 if에서 걸리기 때문에 걱정 없 Arrays.sort(degreeMap, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[degreeVal] - o2[degreeVal]; }
});
// 출력 String result = ""; for(int i=1; i<=N; i++) { if(degreeMap[i][degreeVal] == i-1) { result += degreeMap[i][team] + " "; }else { result = "IMPOSSIBLE"; break; } } System.out.println(result); } } } |
(2) queue 를 이용한 위상정렬
import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class BOJ3665 { public static void main(String[] args) throws Exception{ System.setIn(new FileInputStream("src/input.txt")); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st;
int T = Integer.parseInt(br.readLine()); for(int t=1; t<=T; t++) { int N = Integer.parseInt(br.readLine()); int rank[] = new int[N+1];
st = new StringTokenizer(br.readLine()); for(int i=1; i<=N; i++) { rank[i] = Integer.parseInt(st.nextToken()); }
// map 생성하기 boolean map[][] = new boolean[N+1][N+1]; int indegree[] = new int[N+1]; for(int i=1; i<=N; i++) { int a = rank[i];
for(int j=1; j<i; j++) { int b = rank[j]; map[a][b] = true; indegree[a]++; } }
// 순위 바꾸기 int K = Integer.parseInt(br.readLine()); for(int i=1; i<=K; i++) { st = new StringTokenizer(br.readLine()); int ch1 = Integer.parseInt(st.nextToken()); int ch2 = Integer.parseInt(st.nextToken());
if(map[ch1][ch2]) { indegree[ch1]--; indegree[ch2]++; }else { indegree[ch2]--; indegree[ch1]++; }
map[ch1][ch2] = !map[ch1][ch2]; map[ch2][ch1] = !map[ch2][ch1]; }
// 위상정렬 시작 Queue<Integer> q = new LinkedList<Integer>(); for(int i=1; i<=N; i++) { if(indegree[i]==0) { q.add(i); } }
int loopCnt = 0 ; String resultStr = ""; while(!q.isEmpty()) { // 큐 상태 체크 (순위 데이터이기 때문에 큐에 데이터가 2개 이상 동시에 존재할 수 없다.) if( q.size() >= 2 ) { break; }
loopCnt++; int now = q.poll(); resultStr += now + " ";
for(int i=1; i<=N; i++) { if(map[i][now]) { indegree[i]--; if(indegree[i]==0) { q.add(i); } } } }
if(loopCnt == N) { System.out.println(resultStr); }else { System.out.println("IMPOSSIBLE"); }
} } } |
고찰
"?" 를 출력하는 부분이 없어도 PASS가 됨.
팀의 작년 순위가 주어지기 때문에, 순위를 변경한 후에 '순위'가 제대로 출력되지 못한다면 그건 본부에서 발표한 순위 정보에 일관성이 없기 때문이다.
즉, 순위가 제대로 나오지 않는 다면 "무조건" 데이터의 일관성이 없기 때문이다.
(왜냐, 기존 순위 정보가 항상 올바르게 주어지니까)
(맞게 생각한건지는 잘 모르겠다~~~좀 더 고민이 필요할 듯)
댓글