문제
My Code
import java.io.*;
import java.util.LinkedList;
import java.util.Stack;
public class Main {
static LinkedList<Integer>[] linkedList;
static Stack<Integer> stack;
static int[] result;
static int index = 0;
static boolean[] tf;
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int[] input = new int[2];
stack = new Stack<>();
int count = 0;
//정점과 간선 입력&저장
String str = bf.readLine();
int n = Integer.parseInt(str.split(" ")[0]);
int m = Integer.parseInt(str.split(" ")[1]);
=
//결과 배열 선언
result = new int[n+1];
//true, false판별 배열&인접 리스트 생성 및 초기화
tf = new boolean[n+1];
linkedList = new LinkedList[n+1];
for(int i = 0; i < n+1; i++) {
linkedList[i] = new LinkedList<>();
tf[i] = false;
}
//간선의 양 끝 점 u, v입력&저장
for (int i = 0; i < m; i++) {
String str2 = bf.readLine();
int u = Integer.parseInt(str2.split(" ")[0]);
int v = Integer.parseInt(str2.split(" ")[1]);
if(u==v) return;
addEdge(u, v); //인접 리스트에 u, v 저장
}
//true, false판별
for (int i = 1; i < linkedList.length; i++){
if(tfDivide(i) == 0) continue;
else {
tfDivide(i);
count += 1;
}
}
System.out.println(count);
}
private static int tfDivide(int i) {
//false는 한번도 스택에 저장하지 않은 값 -> 결과 배열에 값 저장
if (tf[i] == false) {
stack.push(i);
tf[i] = true;
result[index] = stack.pop();
index++;
for (int j = 0; j < linkedList[i].size(); j++)
tfDivide(linkedList[i].get(j));
return 1;
}
else{
return 0;
}
}
//인접 노드 더하기
private static void addEdge(int u, int v) {
linkedList[u].add(v);
}
}
문제의 핵심 & 알게된 점
우선 내 코드로 출력은 가능한데 틀렸습니다라고 계속 떴다.
여러 문제가 있었다.
1.
for (int i = 0; i < m; i++) {
String str2 = bf.readLine();
int u = Integer.parseInt(str2.split(" ")[0]);
int v = Integer.parseInt(str2.split(" ")[1]);
if(u==v) return;
addEdge(u, v); //인접 리스트에 u, v 저장
}
여기서
addEdge(u, v); //인접 리스트에 u, v 저장
인접 리스트에 값을 더하는 과정에서 문제가 있었다.
문제는 방향이 없는 그래프가 주어졌다고 했다.
즉, 간선은 두 정점 간의 양방향 연결을 나타내야 하고, 양쪽 방향으로 연결을 표시해야 한다.
한쪽 방향으로만 하면 방향이 있는 그래프가 되기 때문이다.
그래서 addEdge(v, u);를 추가해야한다.
2.
for (int i = 1; i < linkedList.length; i++){
if(tfDivide(i) == 0) continue;
else {
tfDivide(i);
count += 1;
}
}
if문으로 tfDivide()를 호출하고, 그 후 if문 안의 실행문에서도 tfDivide()를 호출한다.
따라서 중복 호출이 발생한다.
그래서 if문 안의 조건을 !tf[i]로 바꿨다.(함수 호출 없이 t, f판별)
3.
private static int tfDivide(int i) {
//false는 한번도 스택에 저장하지 않은 값 -> 결과 배열에 값 저장
if (tf[i] == false) {
stack.push(i);
tf[i] = true;
result[index] = stack.pop();
index++;
for (int j = 0; j < linkedList[i].size(); j++)
tfDivide(linkedList[i].get(j));
return 1;
}
else{
return 0;
}
}
이 함수에서 tf를 판별할 필요는 없다. 위의 if문에서 했기 때문이고 그게 더 효율적이다.
stack은 dfs를 구현하기 위해 사용한 것인데 이 문제에서는 굳이 stack과 result[]를 이용하지 않아도 되서 지웠다.
for (int j = 0; j < linkedList[i].size(); j++)
tfDivide(linkedList[i].get(j));
여기서 바로 tfDivide()를 호출하면 t,f판별이 되지 않기 때문에 if문을 통해 t,f판별을 해야한다.
그리고 이 반복문을 가독성이 높게 수정했다.
for each반복문을 이용했다.
참고로
tf = new boolean[n+1];
linkedList = new LinkedList[n+1];
for(int i = 0; i < n+1; i++) {
linkedList[i] = new LinkedList<>();
tf[i] = false;
}
여기서 tf[i] = false;
는 굳이 없어도 되는 코드다.
이미 선언하면 default 값이 false이기 때문이다.
이와 같은 여러 문제를 고쳐서 밑의 코드로 수정하니 맞았습니다라고 떴다.
힘든 과정이었다...
수정한 Code
import java.io.*;
import java.util.LinkedList;
import java.util.Stack;
public class Main {
static LinkedList<Integer>[] linkedList;
static boolean[] tf;
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
//정점과 간선 입력&저장
String str = bf.readLine();
int n = Integer.parseInt(str.split(" ")[0]);
int m = Integer.parseInt(str.split(" ")[1]);
//true, false판별 배열&인접 리스트 생성 및 초기화
tf = new boolean[n+1];
linkedList = new LinkedList[n+1];
for(int i = 0; i < n+1; i++) {
linkedList[i] = new LinkedList<>();
}
//간선의 양 끝 점 u, v입력&저장
for (int i = 0; i < m; i++) {
String str2 = bf.readLine();
int u = Integer.parseInt(str2.split(" ")[0]);
int v = Integer.parseInt(str2.split(" ")[1]);
addEdge(u, v);
addEdge(v, u);
}
//true, false판별 및 함수 호출
int count = 0;
for (int i = 1; i < linkedList.length; i++){
if(!tf[i]) {
tfDivide(i);
count++;
}
}
System.out.println(count);
}
//dfs방식 함수
private static void tfDivide(int i) {
tf[i] = true;
for (int j : linkedList[i]){
if (!tf[j])tfDivide(j);
}
}
//인접 노드 더하기
private static void addEdge(int u, int v) {
linkedList[u].add(v);
}
}
'Java' 카테고리의 다른 글
[백준] 2178번 미로 탐색 - BFS / 너비 탐색 알고리즘 / 클래스 (0) | 2023.09.05 |
---|---|
[Java] BFS 구현하기 - 재귀 함수&Queue이용 / 인접 리스트 (1) | 2023.09.02 |
[Java] DFS 구현하기 - 재귀 함수 이용 / 인접 리스트 / 배열 (0) | 2023.08.31 |
[백준] 1517번 버블 소트 - 병합 정렬 / 버블 정렬 (0) | 2023.08.31 |
[백준] 11004번 K번째 수 - 퀵정렬 / 오름차순 정렬 (0) | 2023.08.28 |