Sabrina Carpenter-Good Graces
문제 풀면서 들은 노래
https://school.programmers.co.kr/learn/courses/30/lessons/86971?language=java
문제 설명
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결됨.
이 전선들 중 1개를 끊어, 현재의 전력망 네트워크를 2개로 분할하고자 함.
이때, 두 전력망이 갖게되는 송전탑의 개수를 최대한 비슷하게 맞추고자 함.
송전탑 개수:n, 전선 정보: wires, 전선들 중 하나 끊어 송전탑 개수가 비슷해지도록 두 전력망을 나눌때, 두 전력망이 가지고 있는 송전탑 개수 차이(절댓값) return.
생각
2차원 배열인 wires를 어떤 자료구조를 사용해서 저장해야 문제 풀이가 쉬울까..
또, 이렇게 만든 자료구조에서 이어진 전선들 중 어떤 전선을 잘라야 두 전력망이 갖는 노드들의 개수가 비슷할까?..
풀이
그래프를 코드로 나타내는 2가지 방법이 있다.
1. 인접행렬, 2. 인접리스트인데, 간선의 수가 많으면 인접 행렬이 낫고, 간선의 수가 얼마 없을땐 인접리스트 사용이 유리.
해당 문제에서 n이 2이상 100 이하라고 했으니 희소그래프에 해당하므로, 인접리스트
를 사용하자.
인접리스트
를 사용해 그래프(트리) 표현HashMap<Integer, List<Integer>>
를 사용해 각 노드와 연결된 노드 저장정답코드
import java.util.*;
class Solution {
// 1. 인접리스트 생성
HashMap<Integer, List<Integer>> map = new HashMap<>();
public int solution(int n, int[][] wires) {
int answer = -1;
for(int[] wire : wires){
map.putIfAbsent(wire[0], new ArrayList<>());
map.putIfAbsent(wire[1], new ArrayList<>());
map.get(wire[0]).add(wire[1]);
map.get(wire[1]).add(wire[0]); // 양방향 그래프
}
// 2. 각 전선을 하나씩 제거해보고 두 전력망 크기 차이 계산
int minDiff = n; // 크기 차이 최솟값
for(int[] wire: wires){
// 전선 제거
map.get(wire[0]).remove(Integer.valueOf(wire[1]));
map.get(wire[1]).remove(Integer.valueOf(wire[0]));
// bfs로 연결 개수 계산
int size = bfs(wire[0], n);
// 차이 계산
int diff = Math.abs(n- 2*size); // |(n-size)-size|이므로
minDiff = Math.min(diff, minDiff);
// 전선 복구
map.get(wire[0]).add(wire[1]);
map.get(wire[1]).add(wire[0]);
}
return minDiff;
}
// 3. bfs
private int bfs(int start, int n){
Queue<Integer> q = new LinkedList<>(); // 큐 생성
boolean[] visited = new boolean[n+1]; // 방문체크
q.offer(start);
visited[start]=true;
int size = 0; // 크기
while(!q.isEmpty()){
int node = q.poll();
size ++;
// 연결 요소 구하기
for(int nei: map.get(node)){
if(!visited[nei]){
q.offer(nei);
visited[nei]=true;
}
}
}
return size;
}
}
graph.get(wire[0]).remove(Integer.valueOf(wire[1]));
여기서 바로remove(wire[1])
을 안하고Integer.valueOf
를 붙여주는 이유?
의도한 동작:
여기서는 특정 값을 가진 요소를 제거하려고 합니다.
wire은 int 타입이므로, 그대로 사용하면 인덱스로 해석될 수 있습니다.
해결책:
Integer.valueOf(wire) 는 int를 Integer 객체로 변환합니다.
이렇게 하면 remove(Object o) 메소드가 호출되어 의도한 대로 특정 값을 가진 요소를 제거합니다.
예를 들어, wire이 3이고 리스트가 [1, 2, 3, 4]라면:
remove(3)은 인덱스 3의 요소(4)를 제거합니다.
remove(Integer.valueOf(3))은 값이 3인 요소를 제거합니다.
따라서 Integer.valueOf()를 사용하여 명시적으로 객체를 생성함으로써 의도한 대로 특정 값을 가진 요소를 제거.
BFS 기본 코드(java)
import java.util.*;
public class BFS {
public static void bfs(int start, List<List<Integer>> graph, boolean[] visited) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
queue.offer(neighbor);
visited[neighbor] = true;
}
}
}
}
public static void main(String[] args) {
int n = 6; // 노드의 수
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
boolean[] visited = new boolean[n];
bfs(0, graph, visited);
}
}