코딩테스트/BFS & DFS8 [BFS] 전력망을 둘로 나누기 1. 위 문제와 같이 노드와 노드가 연결되어있는 문제의 경우, 인접관계행렬을 만들어 각 노드간 연결되어있을 경우 1, 연결되어있지 않을 경우 0으로 설정해, 배열을 만든다. 2. BFS를 이용해, 선을 하나씩 끊고, 복구하기를 반복하면서 " |두 전력망의 송전탑 개수 차| "가 가장 작은값을 반환한다. 3. BFS / DFS 모두 각 노드를 방문 했는지 안했는지를 나타내는 boolean[] visited를 생성해야 한다. 4. BFS에서는 Queue를 사용하는데, 처음 기준이 되는 노드를 넣어주고, 이 노드와 연결되어 있는 다음 노드를 추가하고 삭제하는데 사용 된다. 코드 import java.util.LinkedList; import java.util.Queue; class Solution { int[.. 2024. 2. 20. DFS / BFS DFS( 깊이 우선 탐색 , Depth-First Search) 루트 노드( 혹은 다른 임의의 노드)에서 다음 분기(branch)로 넘어가기 전에, 해당 분기(branch)를 모두 탐색하는 방법. 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색합니다. 특징 자기 자신을 호출하는 순환 알고리즘의 형태를 지닙니다. (재귀 or 스택) 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것입니다. (이를 검사하지 않을 경우 무한 루프에 빠질 수 있다. ) ex) visit[index] = true; 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로(새로운 분기)로 돌아와.. 2024. 1. 22. 이전 1 2 다음
