오늘의 학습 키워드
</> 깊이/너비 우선 탐색(DFS/BFS)
공부한 내용 본인의 언어로 정리하기
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 총 파이프의 개수
int C = sc.nextInt(); // 분기점의 개수
// 트리를 저장할 HashMap
Map<Integer, List<Integer>> tree = new HashMap<>();
for (int i = 1; i <= N; i++) {
tree.put(i, new ArrayList<>());
}
// 입력 받아서 트리 구조 구성
// 분기점에서 연결된 자식 노드들을 트리에 추가
for (int i = 0; i < C; i++) {
int Ei = sc.nextInt();
int B1i = sc.nextInt();
int B2i = sc.nextInt();
tree.get(Ei).add(B1i);
tree.get(Ei).add(B2i);
}
// BFS를 통한 거리 계산
// 노드 1을 시작 노드로 하여서 각 노드까지의 거리를 계산한다.
int[] distances = bfs(tree, 1, N);
// 결과 출력
for (int i = 1; i <= N; i++) {
System.out.println(distances[i]);
}
}
public static int[] bfs(Map<Integer, List<Integer>> tree, int start, int n) {
//거리 배열 초기화
int[] distance = new int[n + 1];
Arrays.fill(distance, -1); // 초기화: -1은 미방문을 의미
//Queue 초기화
Queue<Integer> queue = new LinkedList<>();
//시작 노드 추가
queue.add(start);
//시작 노드의 거리 1로 설정
distance[start] = 1;
//큐가 빌때까지 탐색
while (!queue.isEmpty()) {
//현재노드 꺼내기
int current = queue.poll();
//현재 노드까지의 거리
int currentDist = distance[current];
// 현재 노드의 모든 자식 노드를 탐색합니다.
List<Integer> children = tree.get(current); // 현재 노드의 자식 리스트 가져오기
for (int i = 0; i < children.size(); i++) {
int child = children.get(i); // 자식 노드 가져오기
if (distance[child] == -1) { // 아직 방문하지 않은 노드
distance[child] = currentDist + 1; // 자식 노드까지의 거리 업데이트
queue.add(child); // 자식 노드를 큐에 추가
}
}
}
return distance;
}
}오늘의 회고
오늘 푼 문제는 주어진 트리 구조에서 각 노드까지의 거리를 계산하는 BFS (너비 우선 탐색) 문제였다.
어떻게 풀어야 할지 감도 안잡혀서 우선 DFS와 BFS에 대해서 먼저 공부를 하고 시작했다.
그 과정에서 최단거리의 탐색에는 BFS가 더 알맞다는 것을 확인하고 천천히 알아보며 진행하였다.
우선 백준에서는 자동으로 입력값을 입력해주지 않기때문에 Scanner를 이용해서 넣어주도록 하였고
HashMap을 이용하여 트리를 생성해주었다.
하지만 BFS를 어떻게 해야하는지도 모르겠고 이해도 안가서 구글 검색의 도움을 많이 받았다.
BFS는 가장 가까운 노드부터 탐색하는 알고리즘으로 선입선출( FIFO )를 원칙으로 한다.
동작방식은 탐색 시작 노드를 큐에 갑입하고 방문처리를 한다. 방문처리란 방문한 값을 기억해준다고 생각하면 될것이다.
그리고 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
이 과정을 더 이상 수행할 수 없을 때까지 반복한다.
그렇게 인접노드를 계속 탐색하며 거리를 +1을 하면서 업데이트를 하였고 각 노드의 거리를 배열로 만들어 반환해주었다.
오늘은 솔직히 100프로 이해가 안되어 누구에게 설명을 해줄 정도로 갖춰지지 못했다...좀 더 많은 경험과 지식이 필요해보인다. 그리고 이게 브론즈 문제라고...? 말도 안돼...
AI 코드리뷰
현재 코드의 장점
-
명확한 구현: 트리 구조를
HashMap을 통해 저장하고, BFS를 사용해 각 노드까지의 거리를 계산하는 과정이 명확하게 구현되었습니다. BFS 알고리즘은 거리를 계산하는 데 있어 적절한 선택입니다. -
BFS의 활용:
BFS는 트리나 그래프에서 최단 경로를 찾는 데 유리한 알고리즘입니다. 이 코드는 이 점을 잘 활용하고 있어, 루트 노드에서 모든 노드까지의 최단 거리를 효율적으로 계산할 수 있습니다. -
모듈화:
BFS를 별도의 메소드로 분리하여, 메인 로직과 거리를 계산하는 로직을 구분했습니다. 이는 코드의 가독성과 재사용성을 높입니다.
현재 코드의 단점
-
초기화의 필요성: 트리 구조를 만들기 위해
for (int i = 1; i <= N; i++)루프에서 각 노드를 초기화하는 부분이 불필요할 수 있습니다. 자식 노드가 없는 경우는 자연스럽게 빈 리스트로 처리되므로, 굳이 모든 노드를 초기화할 필요는 없습니다. -
불필요한 입력 처리: 트리가 완전히 주어지지 않고 일부 노드에만 자식 노드가 있는 경우, 코드가 여전히 모든 노드를 고려하는 방식으로 작성되어 있어, 메모리 효율이 떨어질 수 있습니다.
-
입력 범위에 대한 고려 부족: 입력이 잘못되거나 범위 밖의 값이 주어질 경우에 대한 예외 처리가 없습니다. 이는 프로그램이 예상치 못한 상황에서 충돌하거나 잘못된 결과를 반환할 수 있습니다.
시간 복잡도
- O(N + C)입니다.
- O(N)은 초기화 과정에서, O(C)는
BFS에서 트리의 모든 간선을 따라가며 노드를 방문하는 과정에서 발생합니다. - 트리의 모든 노드를 한 번씩 방문하고, 각 노드의 자식 노드를 탐색하는 비용은 O(N + C)가 됩니다.
개선된 코드 리뷰
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 총 파이프의 개수
int C = sc.nextInt(); // 분기점의 개수
// 트리를 저장할 HashMap
Map<Integer, List<Integer>> tree = new HashMap<>();
// 입력 받아서 트리 구조 구성
for (int i = 0; i < C; i++) {
int Ei = sc.nextInt();
int B1i = sc.nextInt();
int B2i = sc.nextInt();
tree.computeIfAbsent(Ei, k -> new ArrayList<>()).add(B1i);
tree.computeIfAbsent(Ei, k -> new ArrayList<>()).add(B2i);
}
// BFS를 통한 거리 계산
int[] distances = bfs(tree, 1, N);
// 결과 출력
for (int i = 1; i <= N; i++) {
System.out.println(distances[i]);
}
}
public static int[] bfs(Map<Integer, List<Integer>> tree, int start, int n) {
int[] distance = new int[n + 1];
Arrays.fill(distance, -1); // 초기화: -1은 미방문을 의미
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
distance[start] = 1;
while (!queue.isEmpty()) {
int current = queue.poll();
int currentDist = distance[current];
if (!tree.containsKey(current)) continue; // 자식 노드가 없는 경우
for (int child : tree.get(current)) {
if (distance[child] == -1) { // 아직 방문하지 않은 노드
distance[child] = currentDist + 1;
queue.add(child);
}
}
}
return distance;
}
}
개선된 버전의 장점
-
공간 효율성 향상:
computeIfAbsent를 사용하여 실제 필요한 노드만 초기화하므로 메모리를 절약할 수 있습니다. 불필요한 초기화를 방지하여, 입력 데이터가 많을 때 메모리 사용이 최적화됩니다. -
간결한 코드:
computeIfAbsent와 containsKey를 사용해 코드가 간결해졌습니다. 이는 코드의 가독성을 높이고 유지 보수를 쉽게 만듭니다. 불필요한 조건문을 줄여 코드가 더 직관적으로 변했습니다. -
예외 처리 강화:
if (!tree.containsKey(current)) continue;를 통해 자식 노드가 없는 경우를 처리해 불필요한 반복을 줄였습니다. 이는 자식 노드가 없는 노드를 효율적으로 건너뛸 수 있게 하여 실행 시간을 줄이는 데 도움이 됩니다. -
유연한 자료 구조 사용:
HashMap과ArrayList를 사용하여 트리 구조를 유연하게 표현할 수 있습니다. 이 자료 구조는 삽입, 삭제, 검색에 효율적이며 다양한 트리 형태를 쉽게 다룰 수 있습니다.
개선된 버전의 단점
-
공간 복잡도:
HashMap과Queue를 사용하여 추가적인 메모리 사용이 발생합니다. 이는 입력 크기N이 매우 큰 경우, 특히 제한된 메모리 환경에서는 문제가 될 수 있습니다. -
불필요한 초기화:
for루프에서 모든 노드에 대해HashMap을 초기화하는 것은 비효율적입니다. 실제로 존재하지 않는 노드도 초기화하기 때문에 메모리 낭비가 발생할 수 있습니다. 이 문제는 간단한 조건문이나 입력된 노드만 초기화하는 방식으로 해결할 수 있습니다. -
특정 케이스 미처리: 입력 데이터가 잘못된 경우(예: 동일한 자식 노드가 두 번 연결되는 경우)나, 루트 노드(1)로부터 연결되지 않은 노드가 존재하는 경우에 대한 예외 처리가 없습니다.
시간 복잡도
- 시간 복잡도:
- BFS 알고리즘의 시간 복잡도는 O(N + M)입니다. 여기서
N은 노드의 수,M은 간선의 수(이 문제에서는N-1로 간주할 수 있음)입니다. 이 문제에서는M = N - 1이므로 시간 복잡도는 O(N)입니다. - HashMap에 자식 노드를 추가하는 작업은 평균적으로 O(1)입니다.
- 따라서 전체적인 시간 복잡도는 O(N)입니다.
- BFS 알고리즘의 시간 복잡도는 O(N + M)입니다. 여기서
- 공간 복잡도:
- 공간 복잡도는 O(N)입니다.
BFS탐색을 위해HashMap,distance배열,Queue를 사용하므로 각 자료 구조가 N개의 노드를 저장할 수 있어야 합니다.
- 공간 복잡도는 O(N)입니다.
내일 공부할 것 :
DFS와 BFS에 대해서 개념과 동작원리, 구조, DFS와 BFS의 비교, 효율적인 사용처 등 더 자세한 이해를 위해 공부를 해야겠다.
문제
