https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
문제설명
단순 DFS, BFS 구현 문제이다!
문제 해결 방법
DFS는 스택으로, BFS는 큐로 문제를 풀었다. !
코드 구현
package Mar0304;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
public class P_1260 {
public static int N, M, V;
public static boolean[] visited;
public static int[][] graph;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
V = Integer.parseInt(st.nextToken());
visited = new boolean[N];
graph = new int[N][N];
for(int i = 0; i < N; i++) {
visited[i]=false;
Arrays.fill(graph[i], 0);
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph[a-1][b-1] = 1;
graph[b-1][a-1] = 1;
}
DFS(V-1);
Arrays.fill(visited, false);
System.out.println("");
BFS(V-1);
}
// DFS
public static void DFS(int start) {
//visited[start] = true;
Stack<Integer> stack = new Stack<>();
stack.push(start);
while(!stack.isEmpty()) {
int current = stack.pop();
if(!visited[current]) {
System.out.print((current + 1) + " ");
visited[current] = true;
}
for(int i = N - 1; i >= 0; i--) {
if(!visited[i]) {
if(graph[current][i] == 1) {
stack.push(i);
}
}
}
}
}
// BFS
public static void BFS(int start) {
Queue<Integer> q = new LinkedList<Integer>();
//visited[start] = true;
q.offer(start);
while(!q.isEmpty()) {
int nodeIndex = q.poll();
if(!visited[nodeIndex]) {
System.out.print((nodeIndex + 1) + " ");
visited[nodeIndex] = true;
}
for(int i = 0; i < N; i++) {
if(graph[nodeIndex][i]==1 && !visited[i]) {
q.offer(i);
}
}
}
}
}
시간/공간 복잡도
O(N^2)
최적화 및 개선
하지않음
어려웠던 점
문법이 손에 안익어서 어려웠다.
'CodingTest > solved - Java' 카테고리의 다른 글
| [프로그래머스 lv1]두 개 뽑아서 더하기 (0) | 2024.03.08 |
|---|---|
| [백준2667] 단지번호붙이기 (0) | 2024.03.06 |
| [백준2606] 바이러스 (0) | 2024.03.05 |
| [백준2178] 미로 탐색 (0) | 2024.03.05 |
