DFS와 BFS의 기초를 다질 수 있는 문제로서 다양한 풀이 방법을 적용해보았다.
문제
입력 예제
문제 풀이
인접 리스트 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ1260 {
static int n, m, v;
static ArrayList<Integer>[] arr;
static boolean[] dfsVisited;
static boolean[] bfsVisited;
static String dfsOrder;
static String bfsOrder;
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());
arr = new ArrayList[n+1];
dfsVisited = new boolean[n+1];
bfsVisited = new boolean[n+1];
dfsOrder = "";
bfsOrder = "";
for (int i=1; i<=n; i++) {
// 인접 리스트 초기화
arr[i] = new ArrayList<Integer>();
}
for (int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[x].add(y);
arr[y].add(x);
// 오름차순 정렬
Collections.sort(arr[x]);
Collections.sort(arr[y]);
}
DFS(v);
BFS(v);
System.out.println(dfsOrder);
System.out.println(bfsOrder);
}
public static void DFS(int index) {
dfsOrder += index + " ";
if (dfsVisited[index]) {
return;
}
dfsVisited[index] = true;
for (int i: arr[index]) {
if (!dfsVisited[i]) {
DFS(i);
}
}
}
public static void BFS(int node) {
Queue<Integer> queue = new LinkedList<>();
queue.add(node);
bfsVisited[node] = true;
while (!queue.isEmpty()) {
int curr = queue.poll();
bfsOrder += curr + " ";
for (int i: arr[curr]) {
// 방문 조건 : 현재 노드와 다음 노드가 연결된 상태이고 아직 방문하지 않은 상태일 때
if (!bfsVisited[i]) {
bfsVisited[i] = true;
queue.add(i);
}
}
}
}
}
Graph 형식 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ1260_ArrayList {
static int n, m, v;
static boolean[] visited;
static ArrayList<ArrayList<Integer>> graph;
static String dfsOrder;
static String bfsOrder;
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());
dfsOrder = "";
bfsOrder = "";
graph = new ArrayList<>();
visited = new boolean[n+1];
for (int i=0; i<=n; i++) {
// 그래프 초기화
graph.add(new ArrayList<>());
}
for (int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
// 그래프 간 양방향 연결
graph.get(x).add(y);
graph.get(y).add(x);
Collections.sort(graph.get(x));
Collections.sort(graph.get(y));
}
Arrays.fill(visited, false);
DFS(v);
System.out.println(dfsOrder);
Arrays.fill(visited, false);
BFS(v);
System.out.println(bfsOrder);
}
public static void DFS(int node) {
visited[node] = true;
dfsOrder += node + " ";
for (int i: graph.get(node)) {
if (!visited[i]) {
DFS(i);
}
}
}
public static void BFS(int node) {
Queue<Integer> queue = new LinkedList<>();
queue.add(node);
visited[node] = true;
while (!queue.isEmpty()) {
int curr = queue.poll();
bfsOrder += curr + " ";
for (int i: graph.get(curr)) {
if (!visited[i]) {
queue.add(i);
visited[i] = true;
}
}
}
}
}
인접 행렬 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BOJ1260_Array {
static int n, m, v;
static int[][] arr;
static boolean[] visited;
static String dfsOrder;
static String bfsOrder;
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());
arr = new int[n+1][n+1];
visited = new boolean[n+1];
dfsOrder = "";
bfsOrder = "";
for (int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
// 노드 간 양방향 연결
arr[x][y] = arr[y][x] = 1;
// System.out.println("arr check:" + Arrays.toString(arr[x]));
}
Arrays.fill(visited, false);
DFS(v);
System.out.println(dfsOrder);
Arrays.fill(visited, false);
BFS(v);
System.out.println(bfsOrder);
}
public static void DFS(int node) {
visited[node] = true;
dfsOrder += node + " ";
for (int i=1; i<=n; i++) {
// 방문 조건: 서로 양방향으로 연결되어 있고, 이미 방문하지 않은 곳
if (arr[node][i] == 1 && !visited[i]) {
DFS(i);
}
}
}
public static void BFS(int node) {
Queue<Integer> queue = new LinkedList<>();
queue.add(node);
visited[node] = true;
bfsOrder += node + " ";
while (!queue.isEmpty()) {
int curr = queue.poll();
for (int i=1; i<=n; i++) {
if (arr[curr][i] == 1 && !visited[i]) {
queue.add(i);
visited[i] = true;
bfsOrder += i + " ";
}
}
}
}
}
반응형
'Algorithm > Java' 카테고리의 다른 글
[BOJ] 2751. 수 정렬하기2 (0) | 2024.09.12 |
---|---|
[BOJ] 2606. 바이러스 (0) | 2024.08.08 |
[BOJ] 2644. 촌수계산 (1) | 2024.03.05 |
[BOJ] 13305. 주유소 (0) | 2024.01.18 |
[BOJ] 2178. 미로탐색 (0) | 2024.01.17 |