전력망을 둘로 나누기
문제 설명
- wires에 전선으로 연결되어 있는 송전탑이 나와있다. 이 전선을 끊었을 때 나누어지는 송전탑의 갯수가 제일 작은 값을 반환한다.
1번 예제) 4-7을 끊으면 왼쪽에는 1,3,2,4,5,6 탑이 있고 오른쪽에는 7,8,9 탑이 있다. 6-3=3이므로 가장 작은 차이가 난다. 그러므로 답은 3이다.
만약 1-3을 끊는다면 8-1=7이 되므로 답이 될 수 없다.
시행착오 및 문제 풀이
풀이
-
전선으로 연결되어 있는 송전탑 1로 설정하기
1-1. 1-3이 연결되어 있다면 map[1][3] = 1, map[3][1] = 1
반대로도 해주는 이유: 1-3이 연결되어 있으면 3-1이 연결되어 있는거랑 마찬가지이기 때문에 -
for문 돌면서 전선 끊어보기
2-1. 1로 만들어주었던 전선들은 0으로 만든다.
2-2. answer에는 최솟값이 들어가야 하므로 Math.min을 활용하여 가장 작은 값을 넣어준다. 이때 answer은 가장 큰 수인 n으로 초기화해줬다.
2-3. bfs를 통해 해당 송전탑에서 뻗어있는 전선을 찾아서 탑 갯수를 구해준다.
2-4. bfs 탐색을 끝내고 오면 다시 1로 연결시켜준다. (해당 전선을 임의로 끊었기 때문에) -
bfs 탐색해준다.
3-1. 탑의 갯수를 세어 줄 cnt를 선언한다. 이때 나 자신의 송전탑은 방문하면서 시작하므로 cnt=1로 초기화해준다.
3-2. for문을 n까지 돌리면서 연결되어 있고 아직 방문하지 않았다면 cnt++해준다. 그 후 방문처리 해주고 q에 해당 송전탑을 넣어준다.
이때 for문이 1부터 n까지 도는 이유는 인덱스가 아니라 송전탑의 번호로 따지기 때문이다.
3-3. n-2*cnt 반환해준다
cnt는 한 쪽의 송전탑 갯수이다. 이것을 n에서 빼주면 반대편 송전탑 갯수이다.
한쪽: cnt / 반대쪽: n-cnt
이 둘의 차를 구하면 -> n-cnt-cnt = n-2xcnt
이때 어느 쪽이 더 큰 수인지 모르므로 Math.abs()를 통해 절대값 처리한다.
제대로 푼 것 같은데 틀렸다.. why
오답 코드
//bfs
import java.util.*;
class Solution {
static int[][] map;
static boolean[] visited;
public int solution(int n, int[][] wires) {
int answer = n;
map = new int[n+1][n+1];
visited = new boolean[n+1];
//연결되어 있는 부분 1로 설정하기
for(int i=0; i<wires.length; i++) {
map[wires[i][0]][wires[i][1]] = 1;
map[wires[i][1]][wires[i][0]] = 1;
}
//하나씩 끊어보면서 갯수 세기
for(int i=0; i<wires.length; i++) {
//끊기
map[wires[i][0]][wires[i][1]] = 0;
map[wires[i][1]][wires[i][0]] = 0;
answer = Math.min(answer, bfs(wires[i][0], n));
//끊은 전선 다시 되돌리기
map[wires[i][0]][wires[i][1]] = 1;
map[wires[i][1]][wires[i][0]] = 1;
}
return answer;
}
public int bfs(int start, int n) {
Queue<Integer> q = new LinkedList<>();
//시작 넣기
q.offer(start);
//시작 방문 처리
visited[start] = true;
//나를 방문하면서 시작하므로 1부터 시작
int cnt = 1;
while(!q.isEmpty()) {
int temp = q.poll();
for(int i=1; i<n+1; i++) {
//연결되어 있고 방문하지 않았다면 거기서부터 다시 탐색
if(map[temp][i] == 1 && !visited[i]) {
cnt++;
visited[i] = true;
q.offer(i);
}
}
}
return Math.abs(n-2*cnt);
}
}결과
테스트 1
입력값 〉 9, [[1, 3], [2, 3], [3, 4], [4, 5], [4, 6], [4, 7], [7, 8], [7, 9]]
기댓값 〉 3
실행 결과 〉 실행한 결괏값 1이 기댓값 3과 다릅니다.
테스트 2
입력값 〉 4, [[1, 2], [2, 3], [3, 4]]
기댓값 〉 0
실행 결과 〉 실행한 결괏값 2이 기댓값 0과 다릅니다.
테스트 3
입력값 〉 7, [[1, 2], [2, 7], [3, 7], [3, 4], [4, 5], [6, 7]]
기댓값 〉 1
실행 결과 〉 테스트를 통과하였습니다.
테스트 결과 (~˘▾˘)~
3개 중 1개 성공이 부분은 gpt에서 도움을 받았다.
visited 배열이 static으로 선언되어 있고, solution() 메서드에서 단 한 번만 생성되고 있어.
그래서 한 번 bfs()를 돌고 난 다음에 visited에 남은 방문 기록이 다음 bfs()에도 영향을 줘서 오답이 나와.
라고 한다.
아하! 그러니깐 한 쪽의 송전탑을 돌고 계산하고 나오면서 방문 여부가 초기화가 되어야 하는데 난 전역변수로 선언해줘서 초기화가 되지 않았다! 이런 뜻이구나 ㅇㅋㅇㅋ
정답 코드
//bfs
import java.util.*;
class Solution {
static int[][] map;
public int solution(int n, int[][] wires) {
int answer = n;
map = new int[n+1][n+1];
//연결되어 있는 부분 1로 설정하기
for(int i=0; i<wires.length; i++) {
map[wires[i][0]][wires[i][1]] = 1;
map[wires[i][1]][wires[i][0]] = 1;
}
//하나씩 끊어보면서 갯수 세기
for(int i=0; i<wires.length; i++) {
//끊기
map[wires[i][0]][wires[i][1]] = 0;
map[wires[i][1]][wires[i][0]] = 0;
answer = Math.min(answer, bfs(wires[i][0], n));
//끊은 전선 다시 되돌리기
map[wires[i][0]][wires[i][1]] = 1;
map[wires[i][1]][wires[i][0]] = 1;
}
return answer;
}
public int bfs(int start, int n) {
Queue<Integer> q = new LinkedList<>();
//시작 넣기
q.offer(start);
//시작 방문 처리
boolean[] visited = new boolean[n+1];
visited[start] = true;
//나를 방문하면서 시작하므로 1부터 시작
int cnt = 1;
while(!q.isEmpty()) {
int temp = q.poll();
for(int i=1; i<n+1; i++) {
//연결되어 있고 방문하지 않았다면 거기서부터 다시 탐색
if(map[temp][i] == 1 && !visited[i]) {
cnt++;
visited[i] = true;
q.offer(i);
}
}
}
return Math.abs(n-2*cnt);
}
}그래서 bfs 함수가 불러질때마다 boolean visited가 초기화되도록 지역변수로 설정해주었다.
정답!
연결되어 있는 부분을 1로 설정하는 그런 창의적인(?) 사고력은 어떻게 해야 키울 수 있을까..!
사실 이 문제는 예~전에 풀었을 때 너무 힘겹게 풀었던 기억이 있어서 문제가 기억이 났음
풀기 전에 아... 전력망 문제네.... 하면서 굉장히 떨떠름하게 풀었음
bfs인게 기억이 나서 중간중간 여러번 막히긴 했어도 그럼에도 풀긴 했다
어렵다! bfs dfs 너무 싫다 근데 단골문제다ㅜ
