문제 URL
https://www.acmicpc.net/problem/2252
문제 설명 요약
- 키가 작은 학생이 더 큰 학생보다 앞에 서도록 줄 세우기
문제 풀이
- 위상정렬 사용
- 키 비교 값을 방향을 가진 간선 정보로 사용
- indegree의 값을 통해 우선적으로 위치해야 하는 정점들을 파악해나감
- 주어진 키 비교값을 통해 정점간의 선후 관계를 indegree 배열로 표현
만약 1 2 라면 1 -> 2 이므로, 2의 indegree 값에 1이 추가됨 - 맨 처음부터 indegree의 값이 0인 정점들을 모두 큐에 추가
(indegree가 0이라는 것은 곧 반드시 해당 정점보다 앞에 위치해야 하는 정점이 없다는 것과 같은 의미) - 큐가 빌 때까지 돌면서, 큐에서 빼낸 정점에서 뻗어나가는 정점들의 indegree 값을 1 감소시킴
(큐에서 빼낸 정점을 의미적으로 삭제하기 위함) - 감소시킨 indegree값이 0이라면 앞선 로직처럼 큐에 추가
- 주어진 키 비교값을 통해 정점간의 선후 관계를 indegree 배열로 표현
Swift를 활용한 풀이
let nm = readLine()!.split(separator: " ").map{Int($0)!}
var ind = Array(repeating: 0, count: nm[0]+1) // 1-index
var adj:[Int:[Int]] = [:]
for n in 1...nm[0] { adj[n] = [] }
for _ in 0..<nm[1] {
let ab = readLine()!.split(separator: " ").map{Int($0)!}
ind[ab[1]] += 1
adj[ab[0]]!.append(ab[1])
}
var q:[Int] = []
for i in 1...nm[0] {
if(ind[i] == 0) { q.append(i) } // 처음부터 indegree가 0인 정점을 큐에 추가해둠
}
var answer = ""
while(!q.isEmpty) {
// 큐에 추가된 정점을 하나씩 꺼내어, 해당 정점에서 뻗어나가는 정점들의 indegree를 1 감소시킴
// 감소된 indegree값이 0이라면, 해당 정점의 앞에 위치해야 하는 정점들이 모두 사라진 것으로 간주되므로 큐에 추가
let cur = q.removeFirst()
answer += "\(cur) "
for n in adj[cur]! {
ind[n] -= 1
if(ind[n] == 0) { q.append(n) }
}
}
print(answer)
JAVA를 활용한 풀이
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] ind = new int[N+1];
HashMap<Integer, ArrayList<Integer>> adj = new HashMap<>();
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
ind[b]++;
ArrayList<Integer> list = adj.getOrDefault(a, new ArrayList<Integer>());
list.add(b);
adj.put(a, list);
}
Queue<Integer> q = new LinkedList<>();
for(int i=1; i<=N; i++) {
if(ind[i] == 0) q.offer(i);
}
while(!q.isEmpty()) {
int cur = q.poll();
sb.append(cur).append(" ");
if(adj.get(cur) != null) {
for(int n : adj.get(cur)) {
ind[n]--;
if(ind[n] == 0) q.offer(n);
}
}
}
System.out.println(sb);
}
}'Problem Solving' 카테고리의 다른 글
| [SolveSQL] 멘토링 짝꿍 리스트 (0) | 2025.02.17 |
|---|---|
| [SolveSQL] 작품이 없는 작가 찾기 (0) | 2025.02.17 |
| [SolveSQL] 쇼핑몰의 일일 매출액과 ARPPU (0) | 2025.02.06 |
| [SolveSQL] 배송 예정일 예측 성공과 실패 (0) | 2025.02.06 |
| [백준] 1715-카드 정렬하기 (0) | 2025.02.05 |
