깊이우선탐색15 [Baekjoon] 2606 - 바이러스 📝 문제 🔑 풀이 과정 기본적인 DFS 문제. 인접행렬을 이용해 두 노드사이에 간선을 기록 후 시작점인 1인 DFS를 해준다. DFS 완료 후, 방문 배열을 인덱스 2부터 끝까지 검사하면서 방문한 노드(true)의 개수를 세준다. (왜 인덱스 2부터 시작이냐면 구하는 것이 "1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수" 이기 때문에 1번 컴퓨터를 제외한 나머지 컴퓨터의 바이러스 감염 여부를 따지는 것) 🔓 답안 import java.io.*; import java.util.StringTokenizer; public class Main { static int[][] A; static boolean[] visited; public static void main(String[] args) thr.. 2023. 2. 12. [Baekjoon] 11724 - 연결 요소의 개수 📝 문제 ❗ 주의 ArrayList형 배열 A를 사용하기 전에 각 요소를 초기화 시켜줘야 한다. 🔑 풀이 과정 · 연결 요소(Connected Component): 무방향 그래프에서 서로 다른 두 정점이 경로로 연결되어 있으면서 상위 그래프의 추가 정점이 없는 부분 그래프 → 말이 어려울 수 있는데, 그림으로 그렸을때 한 덩어리가 연결 요소이다. 해당 문제 예시 1, 2를 그림으로 표현하면 다음과 같다. 예시 1은 덩어리가 2개 = 연결 요소 2개 예시 2는 덩어리가 1개 = 연결 요소 1개 ArrayList를 사용하여 그래프를 인접리스트로 표현해주었다. 또한 방문 배열을 생성해서 방문시 true, 아직 방문하지 않았으면 false로 표현 이 문제 풀이를 위해 깊이 우선 탐색(DFS)를 사용할 것이다. .. 2023. 2. 3. [알고리즘] 깊이 우선 탐색(DFS) 🟡 깊이 우선 탐색(DFS: depth-first search) - 그래프 완전 탐색 기법 중 하나 - 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 - 재귀 함수로 구현, 스택 자료구조 이용(스택 오버플로에 유의) - 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등의 문제풀이에 사용 🟡 깊이 우선 탐색의 핵심 이론 - DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요 - 그래프는 인접 리스트로 표현(예시 한정) - 후입 선출 특성을 가지므로 스택을 사용하여 설명(실제로는 스택보다는 재귀 함수로 많이 구현) ① DFS를 시작할 노드를 정한 후 사용할 자료.. 2023. 1. 30. 이전 1 2 3 다음
