BOJ - 1260 DFS 와 BFS

pa324·2019년 12월 14일
0

문제

풀이

기본적인 DFS,BFS 구현문제이다. DFS는 재귀호출을 이용하면되고, BFS는 큐를 활용하면 된다.

코드

package algorithm;
import java.util.*;

public class Main {

	static int node [][];
	static boolean[] check;
	static int n;
	static int m;
	static int v;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		v = sc.nextInt();
		
		node = new int[n+1][n+1];
		check = new boolean[n+1];
		
		for(int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			node[a][b] = 1;
			node[b][a] = 1;
		}
		DFS(v);
		check = new boolean[n+1];
		System.out.println();
		BFS(v);
	}
	
	public static void DFS(int v) {
		
		if(check[v] == true) return;
		check[v] = true;
		System.out.print(v+" ");
		for(int i = 1; i <= n; i++) {
			if(node[v][i] == 1 && !check[i]) {
				DFS(i);
			}
		}
		
	}
	
	public static void BFS(int v) {
		Queue <Integer> q = new LinkedList();
		q.add(v);
		check[v] = true;
		System.out.print(v +" ");
		
		int temp;
		while(!q.isEmpty()) {
			temp = q.poll();
			for(int i = 1; i <= n; i++) {
				if(node[temp][i] == 1 && check[i] == false) {
					q.add(i);
					check[i] = true;
					System.out.print(i + " ");
				}
			}
		}
		
	}

}

profile
안녕하세요

0개의 댓글