🔗 백준 13625 - Iks의 체인 오브 커맨드
📌 문제 설명
Iks라는 소셜 네트워크 회사에서는 비표준 관리 시스템을 사용하고 있으며, 특정 직원이 다른 직원들을 직접 또는 간접적으로 관리하는 체계를 갖추고 있다.
두 가지 유형의 명령어를 처리해야 한다.
1. T A B: 직원 A와 B의 위치를 교환한다.
2. P E: 직원 E를 직접 또는 간접적으로 관리하는 사람들 중 가장 어린 관리자의 나이를 출력한다.
🔹 직원의 수는 최대 500명, 관계(M)의 개수는 최대 60,000개, 명령어(I)의 개수는 최대 500개로 주어진다.
🔹 직원들의 관리 관계는 유향 그래프로 표현되며, 관리 관계를 바꾸는 연산(T A B)이 존재하므로 동적 그래프 탐색이 필요하다.
🔍 접근 방식
🔹 1️⃣ 그래프 표현
- 직원들 간의 관리 관계는 인접 행렬(
boolean[][] connMap)을 사용하여 저장했다. connMap[b][a] = true는 a가 b의 직접적인 상사(부모)임을 의미한다.
🔹 2️⃣ 가장 어린 관리자 찾기
- 특정 직원의 모든 상위 관리자(직/간접 관리자)를 탐색하면서 가장 어린 나이를 찾아야 한다.
- 따라서 DFS 탐색을 활용하여 상위 노드들을 방문하면서 최소 나이를 갱신한다.
🔹 3️⃣ 직원 교환 (T A B)
- 직원 A와 B의 위치를 변경하면, A와 B의 부모-자식 관계를 교환해야 한다.
- 단순한 행렬의 Swap이 아니라, 부모-자식 관계를 신중하게 변경해야 함.
- 이를 위해
a, b가 서로 직접적인 연결일 때 별도로 처리하는 로직을 추가하여 반례를 해결했다.
📝 코드 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static StringTokenizer st;
private static StringBuilder sb = new StringBuilder();
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N, M, I;
private static int[] age;
private static boolean[][] connMap;
public static void main(String[] args) throws IOException {
setting();
for (int i = 0; i < I; i++) {
st = new StringTokenizer(br.readLine());
if (st.nextToken().equals("T")) {
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
change(a, b);
} else {
int a = Integer.parseInt(st.nextToken());
int youngestParent = getYoungestParent(a);
sb.append(youngestParent == Integer.MAX_VALUE ? "*" : youngestParent);
if (i != I - 1) sb.append("\n");
}
}
System.out.println(sb.toString());
}
private static int getYoungestParent(int a) {
boolean[] visited = new boolean[N + 1];
visited[a] = true;
return dfs(a, visited, Integer.MAX_VALUE);
}
private static int dfs(int a, boolean[] visited, int minAge) {
for (int i = 1; i < N + 1; i++) {
if (i != a && connMap[a][i] && !visited[i]) {
visited[i] = true;
minAge = Math.min(minAge, dfs(i, visited, age[i]));
}
}
return minAge;
}
private static void change(int a, int b) {
if (a == b) return;
for (int i = 1; i < N + 1; i++) {
if (i == a || i == b) continue;
boolean tmp1 = connMap[i][b];
connMap[i][b] = connMap[i][a];
connMap[i][a] = tmp1;
boolean tmp2 = connMap[b][i];
connMap[b][i] = connMap[a][i];
connMap[a][i] = tmp2;
}
// 반례 발생으로 서로 직접적인 연결일 때, 따로 처리해야 함
// Ex. 2의 부모가 3이 되는 경우는 connMap[2][3]=connMap[2][2]가 되어 오류 발생 가능
boolean tmp = connMap[a][b];
connMap[a][b] = connMap[b][a];
connMap[b][a] = tmp;
}
private static void setting() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
I = Integer.parseInt(st.nextToken());
age = new int[N + 1];
connMap = new boolean[N + 1][N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i < N + 1; i++) {
age[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
connMap[b][a] = true;
}
}
}✅ 핵심 로직 및 해결한 반례
🔹 1️⃣ 직원 교환 시 직접적인 부모-자식 관계 반례 해결
기존 코드에서는 부모-자식 관계가 직접 연결된 경우 오류 발생 가능했다.
예를 들어, 직원 2의 부모가 3인 상황에서 change(2, 3)을 실행하면:
connMap[2][3] = connMap[2][2]; // 잘못된 값이 할당됨이를 방지하기 위해 A와 B가 직접 연결된 경우 따로 처리하여 해결함.
🧐 추가적으로 최적화할 수 있는 부분
1️⃣ 인접 리스트(List<Integer>[] graph)를 사용하여 메모리 최적화 가능
현재 boolean[][] connMap을 사용하면 O(N²) 공간을 차지함.
하지만 List<Integer>[]를 사용하면 연결된 노드만 저장하므로 공간을 줄일 수 있음.
private static List<Integer>[] graph;이렇게 변경하면 DFS 탐색 시에도 graph[node]만 조회하면 되므로 연산 속도가 향상될 수 있음.
2️⃣ BFS를 활용하여 탐색 속도 개선 가능
현재 DFS를 사용하지만, 관리 관계는 트리 구조이므로 BFS를 사용하면 더 빠르게 탐색 가능.
private static int bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
boolean[] visited = new boolean[N + 1];
visited[start] = true;
int minAge = Integer.MAX_VALUE;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int manager : graph[node]) {
if (!visited[manager]) {
visited[manager] = true;
minAge = Math.min(minAge, age[manager]);
queue.add(manager);
}
}
}
return minAge;
}DFS 대신 BFS를 사용하면 더 최적화할 수 있음.
실제 비교해본 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static StringTokenizer st;
private static StringBuilder sb = new StringBuilder();
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N, M, I;
private static int[] age;
private static boolean[][] connMap;
public static void main(String[] args) throws IOException {
setting();
for (int i = 0; i < I; i++) {
st = new StringTokenizer(br.readLine());
if (st.nextToken().equals("T")) {
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
change(a, b);
} else {
int a = Integer.parseInt(st.nextToken());
int youngestParent = getYoungestParent(a);
sb.append(youngestParent == Integer.MAX_VALUE ? "*" : youngestParent);
if (i != I - 1) sb.append(("\n"));
}
}
System.out.println(sb.toString());
// printMap();
}
private static int getYoungestParent(int a) {
boolean[] visited = new boolean[N + 1];
visited[a] = true;
return bfs(a);
}
private static int bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
boolean[] visited = new boolean[N + 1];
visited[start] = true;
int minAge = Integer.MAX_VALUE;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int i = 1; i < N + 1; i++) {
if (connMap[node][i]) {
int manager = i;
if (!visited[manager]) {
visited[manager] = true;
minAge = Math.min(minAge, age[manager]);
queue.add(manager);
}
}
}
}
return minAge;
}
private static void change(int a, int b) {
if (a == b) return;
for (int i = 1; i < N + 1; i++) {
if (i == a || i == b) continue;
boolean tmp1 = connMap[i][b];
connMap[i][b] = connMap[i][a];
connMap[i][a] = tmp1;
boolean tmp2 = connMap[b][i];
connMap[b][i] = connMap[a][i];
connMap[a][i] = tmp2;
}
//반례 발생으로 서로 같은 경우가 되었을때에는 나눠서 정리해준다
//Ex. 2의 부모가 3이되는 경우는 위에 코드를 실행하면 connMap[2][3]=connMap[2][2]가 되기때문에 a,b가 서로 직접적인 연결일때에는 나눠서 처리한다.
boolean tmp = connMap[a][b];
connMap[a][b] = connMap[b][a];
connMap[b][a] = tmp;
}
private static void setting() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
I = Integer.parseInt(st.nextToken());
age = new int[N + 1];
connMap = new boolean[N + 1][N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i < N + 1; i++) {
age[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
connMap[b][a] = true;
}
// printMap();
}
private static void printMap() {
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
System.out.print(connMap[i][j] + " ");
}
System.out.println();
}
}
}실제로 BFS 코드를 작성했을때 속도 비교
BFS가 엄청나게 차이나는 속도를 아니라고 생각
🚀 결론
✅ 인접 행렬을 사용하여 그래프를 저장하고, DFS로 관리 관계를 탐색
✅ T A B에서 직접적인 부모-자식 관계 변경 시 발생하는 반례 해결
✅ 최적화 가능성: 인접 리스트 + BFS를 사용하면 속도 향상 가능
멋있는 사람 - 일단 하자