알고리즘(BOJ)/Silver
백준 - 1260(DFS&BFS)
ch.0
2023. 1. 21. 15:08
문제 분석
DFS에서도 방문여부를 체크 해줘야 했다. 이미 출력한 정점은 또다시 방문하지 않기 위함이다.
처음에는 배열에 정점의 값을 넣어주려고 했지만, 배열의 위치에 1을 넣어주는게 일반적인것 같다.
탐색순서
전체 소스
import java.io.*;
import java.util.*;
public class Main {
static int[][] array;
static int repeat;
static int dat;
static int[] visited;
static boolean[] check;
public static void dfs(int point) {
visited[point] = 1;
System.out.print(point + " ");
for (int i = 1; i <= dat; i++) {
if (array[point][i] == 1 && visited[i] == 0) {
dfs(i);
}
}
}
public static void bfs(int point) {
Queue<Integer> q = new LinkedList<>();
q.offer(point);
check[point] = true;
while (!q.isEmpty()) {
point = q.poll();
System.out.print(point + " ");
for (int i = 1; i <= dat; i++) {
if (array[point][i] == 1 && check[i] == false) {
q.offer(i);
check[i] = true;
}
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
dat = Integer.parseInt(st.nextToken());
repeat = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());
array = new int[dat + 1][dat + 1];
visited = new int[dat + 1];
check = new boolean[dat + 1];
for (int i = 0; i < repeat; i++) {
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
array[x][y] = array[y][x] = 1;
}
dfs(start);
System.out.println();
bfs(start);
}
}