문제 접근
DFS
- 이미 방문한 노드라면 그냥 return
- 아니면 visit 배열을 true로 바꿔주고, StringBuilder에 추가
- 해당 노드의 인접리스트를 돌면서 방문하지 않은 노드에 대하여 DFS()를 실행 (재귀)
BFS
- 맨 처음에 시작노드를 큐에
- while문은 큐가 empty 될때까지 반복
While문 내부
- 꺼내면서 값을 저장
- 꺼냈는데 visit 배열이 false면 StringBuilder에 추가, true로
- now 노드의 인접리스트를 돌면서 방문하지 않은 노드가 있다면 큐에
- 반복
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class S1260 {
static int N, M, V;
static boolean[] visit1, visit2;
static ArrayList<Integer>[] edgeList;
static Queue<Integer> queue = new LinkedList<>();
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
V = Integer.parseInt(st.nextToken());
visit1 = new boolean[N + 1];
visit2 = new boolean[N + 1];
edgeList = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
edgeList[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
edgeList[from].add(to);
edgeList[to].add(from);
}
for (int i = 1; i <= N; i++) {
edgeList[i].sort(Comparator.naturalOrder());
}
dfs(V);
sb.append("\n");
bfs(V);
System.out.println(sb);
}
static void dfs(int start) {
if (visit1[start]) {
return;
}
visit1[start] = true;
sb.append(start).append(" ");
for (int to : edgeList[start]) {
if (!visit1[to]) {
dfs(to);
}
}
}
static void bfs(int start) {
queue.offer(start);
while (!queue.isEmpty()) {
int now = queue.poll();
if (!visit2[now]) {
sb.append(now).append(" ");
}
visit2[now] = true;
for (int to : edgeList[now]) {
if (!visit2[to]) {
queue.offer(to);
}
}
}
}
}
'Algorithm' 카테고리의 다른 글
그래프 / 백준 1707 이분 그래프 (0) | 2025.06.09 |
---|---|
그래프 / 백준 11724 연결 요소의 개수 (0) | 2025.06.08 |
그래프 / 백준 13023 ABCDE (0) | 2025.06.05 |
BF / 백준 6603 로또 (0) | 2025.06.05 |
BF / 백준 10971 외판원 순회 2 (0) | 2025.06.05 |