티스토리 뷰
1. 그래프 + 스택을 이용한 DFS & BFS
package StudyJava.DFSBFS;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Stack;
class Queue<T> { ... } // 생략
class Graph {
class Node { // 그래프 노드 :D
int data;
LinkedList<Node> adjacent;
boolean marked;
Node (int data) { // 생성자
this.data = data;
this.marked = false;
adjacent = new LinkedList<Node>();
}
}
Node[] nodes;
Graph(int size) { // 생성자
nodes = new Node[size];
for(int i = 0; i < size; i++) {
nodes[i] = new Node(i);
}
}
void addEdge(int i1, int i2) { // 노드 연결
Node n1 = nodes[i1];
Node n2 = nodes[i2];
if(!n1.adjacent.contains(n2)) { // n1노드와 n2노드가 연결되어 있지 않다면
n1.adjacent.add(n2); // 연결 추가
}
if(!n2.adjacent.contains(n1)) {
n2.adjacent.addFirst(n1);
}
}
void dfs() {
dfs(0);
}
void dfs(int index) {
Node root = nodes[index];
Stack<Node> stack = new Stack<>();
stack.push(root);
root.marked = true;
while(!stack.isEmpty()) {
Node r = stack.pop();
for(Node n : r.adjacent) {
if(n.marked == false) {
n.marked = true;
stack.push(n);
}
}
visit(r);
}
}
void bfs() {
bfs(0);
}
void bfs(int index) {
Node root = nodes[index];
Queue<Node> queue = new Queue<>();
queue.add(root);
root.marked = true;
while(!queue.isEmpty()) {
Node r = queue.remove();
for(Node n : r.adjacent) {
if(n.marked == false) {
n.marked = true;
queue.add(n);
}
}
visit(r);
}
}
void visit(Node r) {
System.out.print(r.data + " ");
}
void dfsR(Node r) { // 재귀함수를 이용한 dfs (=스택)
if(r == null) return;
r.marked = true;
visit(r);
for(Node n : r.adjacent) {
if(n.marked == false) {
dfsR(n);
}
}
}
void dfsR(int index) {
Node r = nodes[index];
dfsR(r);
}
void dfsR() {
dfsR(0);
}
}
public class MainClass {
public static void main(String[] args) {
Graph g = new Graph(9);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(2, 4);
g.addEdge(3, 4);
g.addEdge(3, 5);
g.addEdge(5, 6);
g.addEdge(5, 7);
g.addEdge(6, 8);
g.dfsR();
}
}
2. 인접행렬을 이용한 DFS BFS (백준 1260번)
package CodingTestMemory.BJ.BFSDFS.P1260;
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
public class P1260 {
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static boolean[] visited;
static int[][] graph;
public static void bfs(int idx) throws IOException {
Queue<Integer> queue = new LinkedList<>();
queue.add(idx);
visited[idx] = true;
while(!queue.isEmpty()) {
int e = queue.remove();
bw.write(String.valueOf(e) + " ");
for(int i = 1; i < visited.length; i++) {
if(!visited[i] && graph[e][i] != 0) {
queue.add(i);
visited[i] = true;
}
}
}
}
public static void dfs(int idx) throws IOException {
for(int i = 1; i < visited.length; i++) {
if(visited[i] || graph[idx][i] == 0) {
continue;
}
bw.write(String.valueOf(i) + " ");
visited[i] = true;
dfs(i);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
int N = Integer.parseInt(stk.nextToken());
int M = Integer.parseInt(stk.nextToken());
int V = Integer.parseInt(stk.nextToken());
int a, b;
graph = new int[N + 1][N + 1];
visited = new boolean[N + 1];
for(int i = 0; i < M; i++) {
stk = new StringTokenizer(br.readLine());
a = Integer.parseInt(stk.nextToken());
b = Integer.parseInt(stk.nextToken());
graph[a][b] = 1;
graph[b][a] = 1;
}
visited[V] = true;
bw.write(String.valueOf(V) + " ");
dfs(V);
visited = new boolean[N + 1];
bw.newLine();
bfs(V);
bw.flush();
bw.close();
}
}* dfs를 재귀적 방법으로 사용할때는 1번 노드부터 탐색하기 위해서는 dfs 호출전에 1번노드를 미리 찍고 시작해야된다
3. BFS 활용 - 1. 백준 2667
package CodingTestMemory.BJ.BFSDFS.P2667;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class P2667 {
static class Node {
int y, x;
Node (int y, int x) {
this.y = y;
this.x = x;
}
}
static int[][] graph;
static boolean[][] visited;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int N;
public static int bfs(int y, int x) {
int cnt = 0;
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(y, x));
visited[y][x] = true;
while(!queue.isEmpty()) {
Node e = queue.poll();
cnt++;
for(int i = 0; i < 4; i++) {
int nx = e.x + dx[i];
int ny = e.y + dy[i];
if(nx < 0 || ny < 0 || nx >= N || ny >= N) {
continue;
}
if(visited[ny][nx] || graph[ny][nx] == 0) {
continue;
}
visited[ny][nx] = true;
queue.add(new Node(ny, nx));
}
}
return cnt;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
String input;
graph = new int[N][N];
visited = new boolean[N][N];
List list = new LinkedList();
for(int j = 0; j < N; j++) { // 데이터 입력
input = br.readLine();
for(int i = 0; i < input.length(); i++) {
graph[j][i] = (int) input.charAt(i) - 48;
}
}
for(int j = 0; j < N; j++) {
for(int i = 0; i < N; i++) { // 시작점 탐색 후 bfs
if(graph[j][i] == 1 && !visited[j][i]) {
list.add(bfs(j, i));
}
}
}
list.sort(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return (int)o1 - (int) o2;
}
});
//Collections.sort(list); // 연결리스트를 정렬하기 위해서는 Collections.sort 를 사용하면 더 편리
System.out.println(list.size()); // 결과 출력부분
for(int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}* 연결리스트를 정렬하는 방법
1. Linkedlist.sort() 사용. Comparator를 직접 정의해 줘야함
2. Collections.sort() 사용. 필요시 Comparator를 직접 정의해서 사용하면 됨.
댓글