파이썬으로 공부했던 알고리즘을 java로도 공부중이다.
파이썬의 간편한 문법에 익숙해져 있어서 java로 하니까 좀 헷갈리지만
알고리즘은 구현방법은 비슷하기 때문에 정리해보려고 한다.
백준의 그래프 문제(1260번: DFS와 BFS (acmicpc.net))로 연습하였다.
코드는 아래와 같다.
package graph_bfs_dfs;
import java.util.*;
import java.io.*;
public class Aug5Week_1260_Ssi {
//두개의 그래프를 출력해야 하기 때문에 변수 선언
public static ArrayList<Integer>[] graph;
public static boolean[] visited;
//재귀를 활용한 dfs
public static void dfs(int v){
System.out.print(v+" ");
visited[v] = true;
for(int n: graph[v]){
if(visited[n] == false){
dfs(n);
}
}
}
public static void bfs(int v){
Queue<Integer> q = new LinkedList<Integer>();
q.add(v);
visited[v] = true;
while(!q.isEmpty()){
int n = q.poll();
System.out.print(n+" ");
for(int i : graph[n]){
if(visited[i] == false){
visited[i] = true;
q.add(i);
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String [] input = bf.readLine().split(" ");
int n = Integer.parseInt(input[0]);
int m = Integer.parseInt(input[1]);
int v = Integer.parseInt(input[2]);
graph = new ArrayList[n+1];
visited = new boolean[n+1];
for(int i=1; i<n+1;i++){
graph[i] = new ArrayList<Integer>();
}
for(int i=0; i<m; i++){
StringTokenizer t = new StringTokenizer(bf.readLine());
int x = Integer.parseInt(t.nextToken());
int y = Integer.parseInt(t.nextToken());
//양방향 그래프
graph[x].add(y);
graph[y].add(x);
}
// 정렬
for(int i=1;i<n+1;i++){
Collections.sort(graph[i]);
}
//출력
dfs(v);
Arrays.fill(visited, false);
System.out.println();
bfs(v);
}
}
dfs와 bfs 모두 구현해야 하는데
dfs의 경우 재귀를 활용한 방식으로 구현하였고
입력받는 그래프와 방문 여부를 체크할 boolean 배열은 공통으로 활용하였다.
728x90
'자료구조 & 알고리즘 & cs > CodingTest' 카테고리의 다른 글
[java/python] 4963 - 섬의 개수 (0) | 2023.09.01 |
---|---|
[python] 1374 - 강의실 (0) | 2023.08.27 |
[python] 2014 - 소수의 곱 (0) | 2023.08.23 |
[python] 1051- 숫자 정사각형 (0) | 2023.07.11 |
[python] 1527 - 금민수의 개수 (0) | 2023.07.03 |