💡 백준 10159번 - 저울 🚀
🔗 문제 링크
📌 문제 설명
N개의 물건이 있고,M개의 비교 결과가 주어진다.- 각 비교 결과는 "A가 B보다 무겁다"는 형태.
- 모든 비교 결과를 바탕으로, 각 물건이 무게 비교를 할 수 없는 개수를 출력하는 문제.
💡 접근 방법
1️⃣ 그래프 탐색 (DFS) 활용
connInfo[i]리스트를 사용하여 i번 물건보다 무거운 물건들을 저장.dfs(i, i, visited)를 호출하여 모든 연결된 물건을 방문하여 개수를 카운트.inCnt[i]: i번 물건보다 무거운 물건 개수outCnt[i]: i번 물건보다 가벼운 물건 개수- 비교가 불가능한 개수 =
N-1 - (inCnt[i] + outCnt[i])
📝 코드 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
private static StringTokenizer st;
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N, M;
private static List<List<Integer>> connInfo = new ArrayList<>();
private static int[] inCnt, outCnt;
public static void main(String[] args) throws IOException {
setting();
// DFS 탐색을 통해 모든 연결 관계 파악
for (int i = 1; i <= N; i++) {
boolean[] visited = new boolean[N + 1];
dfs(i, i, visited);
}
// 비교할 수 없는 개수 출력
for (int i = 1; i <= N; i++) {
System.out.println(N - 1 - inCnt[i] - outCnt[i]);
}
}
private static void dfs(int cur, int start, boolean[] visited) {
for (Integer next : connInfo.get(cur)) {
if (visited[next]) continue;
visited[next] = true;
inCnt[next]++; // 현재 물건보다 무거운 물건 개수 증가
outCnt[start]++; // 시작 물건보다 가벼운 물건 개수 증가
dfs(next, start, visited);
}
}
private static void setting() throws IOException {
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
inCnt = new int[N + 1];
outCnt = new int[N + 1];
// 그래프 초기화
for (int i = 0; i <= N; i++) {
connInfo.add(new ArrayList<>());
}
// 입력 처리 (B가 A보다 무겁다면, connInfo[B]에 A를 저장)
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
connInfo.get(b).add(a);
}
}
}🔍 코드 설명
🔹 DFS 탐색을 활용한 풀이
-
입력값 처리
connInfo[i]: i번 물건보다 무거운 물건들 저장.inCnt[i]: i번 물건보다 무거운 물건 개수.outCnt[i]: i번 물건보다 가벼운 물건 개수.
-
DFS로 모든 연결된 물건 찾기
dfs(i, i, visited)호출하여 모든 연결된 물건을 방문.- 방문한 노드는
inCnt[next]와outCnt[start]값을 증가.
-
결과 출력
- 비교할 수 없는 물건 개수 =
N-1 - (inCnt[i] + outCnt[i])
- 비교할 수 없는 물건 개수 =
🛠 최적화 및 개선 가능성
✅ 1️⃣ 플로이드 와샬(Floyd-Warshall) 알고리즘 사용
현재 DFS 탐색을 N번 수행하기 때문에 시간복잡도가 O(NM) 입니다.
대신, 플로이드 와샬을 사용하면 O(N^3)로 구현 가능하며, 그래프 탐색보다 직관적일 수 있음.
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 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N, M;
private static boolean[][] connInfo;
private static int[] inCnt, outCnt;
public static void main(String[] args) throws IOException {
setting();
// for (int i = 1; i < N + 1; i++) {
// for (int j = 1; j < N + 1; j++) {
// if (i == j) continue;
// for (int k = 1; k < N + 1; k++) {
// if (i == k || j == k) continue;
// if (connInfo[i][j] && connInfo[j][k]) {
// connInfo[i][k] = true;
// }
// }
// }
// }
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
for (int k = 1; k < N + 1; k++) {
if (connInfo[j][i] && connInfo[i][k]) {
connInfo[j][k] = true;
}
}
}
}
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
if (connInfo[i][j]) {
inCnt[j]++;
outCnt[i]++;
}
}
}
for (int i = 1; i < N + 1; i++) {
System.out.println(N - 1 - inCnt[i] - outCnt[i]);
}
}
private static void setting() throws IOException {
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
inCnt = new int[N + 1];
outCnt = new int[N + 1];
connInfo = new boolean[N + 1][N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
connInfo[b][a] = true;
}
}
}
💣 주석 부분!!
// for (int i = 1; i < N + 1; i++) {
// for (int j = 1; j < N + 1; j++) {
// if (i == j) continue;
// for (int k = 1; k < N + 1; k++) {
// if (i == k || j == k) continue;
// if (connInfo[i][j] && connInfo[j][k]) {
// connInfo[i][k] = true;
// }
// }
// }
// }위 코드를 사용하면 틀렸는데 그 이유는?
📌 출발 노드를
i로 설정했을 때의 문제점만약
1 → 4 → 2 → 5와 같은 경로가 있다고 가정해봅시다.
1️⃣ 출발 노드를i로 설정하면for (int i = 1; i <= N; i++) { // 🔴 i를 출발 노드로 설정 (잘못된 방식) for (int j = 1; j <= N; j++) { // 중간 노드 for (int k = 1; k <= N; k++) { // 도착 노드 if (connInfo[i][j] && connInfo[j][k]) { connInfo[i][k] = true; } } } }
- 이 경우,
i가 출발 노드이므로 1 → 4를 확인할 수는 있음.- 하지만 1 → 2 → 5의 경우를 추가할 수 없음.
(1과 2가 직접 연결되지 않았기 때문)
즉, 출발 노드를 기준으로 경로 확장을 하면 연쇄적인 관계를 반영할 수 없음. ❌2️⃣ 경유 노드를
i로 설정하면for (int i = 1; i <= N; i++) { // 🔵 i를 경유 노드로 설정 (올바른 방식) for (int j = 1; j <= N; j++) { // 출발 노드 for (int k = 1; k <= N; k++) { // 도착 노드 if (connInfo[j][i] && connInfo[i][k]) { connInfo[j][k] = true; } } } }
i = 4일 때, 1 → 4와 4 → 2를 연결하여 1 → 2를 갱신할 수 있음.i = 2일 때, 1 → 2와 2 → 5를 연결하여 1 → 5를 갱신할 수 있음.- 결과적으로 모든 연결 관계가 올바르게 확장됨! ✅
🚀 결론
💡 출발 노드를 i로 설정하면 1 → 2 → 5와 같은 경로를 인식하지 못하는 경우가 발생할 수 있다.
이는 1과 2가 직접 연결되지 않았기 때문에 1 → 4 → 2 → 5라는 간접적인 경로를 반영하지 못하기 때문이다.
✅ 경유 노드를 i로 설정하면 1 → 4 → 2 → 5처럼 연쇄적인 연결 관계를 올바르게 확장할 수 있다.
따라서 플로이드-워셜 알고리즘에서는 i를 출발 노드가 아닌 "경유 노드"로 설정해야 한다. 🚀
동그라미 친 부분이 플로이드 워셜을 사용한 것
✅ 2️⃣ BFS로 변경 가능
DFS를 사용하면 재귀 호출이 많아질 경우 스택 오버플로우 발생 가능.
따라서 BFS로 변경하면 스택 문제 없이 해결 가능.
private static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
boolean[] visited = new boolean[N + 1];
visited[start] = true;
while (!queue.isEmpty()) {
int cur = queue.poll();
for (Integer next : connInfo.get(cur)) {
if (!visited[next]) {
visited[next] = true;
inCnt[next]++;
outCnt[start]++;
queue.add(next);
}
}
}
}⏳ 시간복잡도 분석
O(NM): DFS 탐색O(N^3): 플로이드 와샬 (더 직관적이지만 속도 차이는 크지 않음)
🎯 결론
✅ DFS 또는 BFS를 활용하여 그래프 탐색 문제를 해결!
✅ 모든 물건의 무게 관계를 파악한 후, 비교할 수 없는 개수를 출력!
✅ 플로이드 와샬을 활용하면 더 직관적으로 구현 가능! 🚀
멋있는 사람 - 일단 하자