728x90 깊이 우선 탐색4 [1260] DFS와 BFS (JAVA) # 문제 설명 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면.. 2024. 3. 31. [11724] 연결 요소의 개수 (JAVA) # 문제 설명 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. # 정답 코드 import java.io.*; import java.util.*; public class Main { static boolean[] visited; //방문 체크 배열(1~N) static ArrayList[] A; //인접 리스트(1~N) public.. 2024. 3. 29. Day-8 깊이 우선 탐색 DFS 1. 깊이 우선 탐색 DFS(depth-first search)는 그래프 완전 탐색 기법 중 하나이다. 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하고 최대 깊이까지 탐색하는 과정을 반복한다. 재귀 함수로 구현한다. 스택을 이용한다. 시간 복잡도는 O(노드 수 + 엣지 수)이다. 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 문제에 사용할 수 있다. 2. 깊이 우선 탐색 과정 DFS를 위해 필요한 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드를 스택에 삽입하기이다. 위와 같이 초기 작업을 끝냈으면 스택에서 노드를 꺼내고 꺼낸 노드의 인접 노드를 다시 스택에 삽입한다. 스택에 있는 1을 꺼내고 1의 인접 노드인 2, 3을 스택에 추가했다. 또한 2, 3을 방문 배열에서.. 2024. 3. 29. [2606] 바이러스 (JAVA) # 문제 설명 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴.. 2024. 3. 29. 이전 1 다음 728x90
