[백준]2252번 줄세우기
[백준]2252번 줄세우기
문제 이해하기
- N명의 학생들을 “키 순서대로” 줄을 세울 것. 그런데 “키를 직접 재는 것이 아님”
- 두 학생의 키를 “비교” 하여 줄을 세울 것.
- 심지어 “일부 학생들의 키만” 비교 해 봄.
- 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램 작성하기
일부만 주어졌다는 것은 , 주어진 일부 외의 학생들은 “그 순서가 어떻게 되던 상관없다” 는 것으로 이해할 수 있을 듯 하다 → 따라서 정답은 여러가지가 될 수 있다.
- 문제에서도 “출력”에 [ 답이 여러가지인 경우 아무거나 출력한다 ] 라고 되어있다.
- 주어지는 문제의 조건
- A B —→ A가 학생 B의 앞에 서야 한다.
문제 풀이
(:40)
어떤 순서를 만들어야 하는데, “조건”이 주어진다.
조건이 몇개 주어지며 조건을 만족하는 정답은 여러개가 나올 수 있다.
이 문제는 위상정렬 문제다
-
위상정렬로 풀이할 경우 , N(32000)+M(간선의개수==조건의개수==10만) 으로 풀 수 있다.
-
아직은 위상정렬을 바로 구현하는 부분에 있어 느리다는 것을 알 수 있었다.
import java.io.*;
import java.util.*;
public class Main {
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static int parseInt(String target){ return Integer.parseInt(target);}
public static StringTokenizer st;
public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static int n; // 학생 수
public static List<Integer>[] preCondition = new List[32001];
public static int[] ans; // 정답인 순서
public static int[] cnt; // 각 노드의 진입차수
public static void setting() throws IOException {
st = new StringTokenizer(br.readLine());
int m = 0; // 조건의 개수
int a=0,b=0; // a 는 b 의 조건
// n 과 m : n 은 학생 수, m 은 조건의 개수
n = parseInt(st.nextToken());
m = parseInt(st.nextToken());
// Init
ans = new int[n];
cnt = new int[n+1];
// Init preCondition
for (int i=1; i <= n;i++){
// i 를 조건으로 갖는 노드들의 List 를 초기화
preCondition[i] = new ArrayList<>();
}
// 각 조건의 형태 : A B --> A 는 B의 앞에 있어야 한다는 조건 --> A 는 B의 조건이다
for (int i =0;i<m;i++){
st = new StringTokenizer(br.readLine());
a = parseInt(st.nextToken());
b = parseInt(st.nextToken());
preCondition[a].add(b); // a 를 조건으로 갖는 노드를 추가
cnt[b]++; // b 의 진입차수를 1 증가
}
}
public static void solve(){
LinkedList<Integer> q = new LinkedList<>();
// 진입 차수가 0인 노드들을 큐에 넣고 시작한다
for ( int i =1; i <= n; i++){
if (cnt[i]==0) q.add(i);
}
// q 에서 n 개의 노드를 뽑아 낼 수 있어야 한다.
int cur = -1,order = 0;
for (int i =0; i<n;i++){
cur = q.poll();
ans[order++] = cur;
// 이 노드를 조건으로 갖는 노드들의 진입 차수를 1감소
for (Integer adj : preCondition[cur]) {
cnt[adj]--;
// 감소시킨 후 진입차수가 0이 된 노드를 q 에 삽입
if (cnt[adj] ==0) q.add(adj);
}
}
}
public static void printOrder() throws IOException{
for(int i =0;i<n;i++){
bw.write(ans[i]+" ");
}
bw.flush();
bw.close();
}
public static void main(String[] args)throws IOException {
setting();
solve();
printOrder();
}
}
Author And Source
이 문제에 관하여([백준]2252번 줄세우기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ynoolee/백준2252번-줄세우기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)