[백준_1260] DFSBFS

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

문제풀이

• 노드연결이 중요함.
• dfs/bfs 이해
• check 배열 중요 !

1	2	3	4
2	1	1	1
3	4	4	2
4			3

 

DFS : 1->2->4->3

BFS : 1->2->3->4 //1에서 이미 다 Queue에 들어가면서 방문.

 

C++

 

 

Java

package Z_ShinHanCard_Prepare;

import java.util.*;

public class D2백준1260_DFSBFS {
	static int N, M, K;
	static boolean[] check;
	static ArrayList<Integer>[] arr;

	public static void dfs(int s) {
		if (check[s])
			return;
		check[s] = true;
		System.out.print(s + " ");
		for (int y : arr[s]) {
			if (check[y] == false) {
				dfs(y);
			}
		}
	}

	public static void bfs(int s) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(s);
		
		check[s] = true;
		while (!q.isEmpty()) {
			int x = q.poll();			
			System.out.print(x+" ");
			for (int w = 0; w < arr[x].size(); w++) 
			{
				int nx = arr[x].get(w);
				if (check[nx])
					continue; 
				q.add(nx);
				check[nx] = true; 
			}

		}

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		// TODO Auto-generated method stub
		N = sc.nextInt();
		M = sc.nextInt();
		K = sc.nextInt();
		arr = new ArrayList[N + 1];

		for (int i = 0; i <= N; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < M; i++) {
			int u, v;
			u = sc.nextInt();
			v = sc.nextInt();
			arr[u].add(v);
			arr[v].add(u);
		}
		for (int i = 0; i < arr.length; i++) {
			Collections.sort(arr[i]);
		}
		check = new boolean[N + 1];
		dfs(K);
		check = new boolean[N + 1];
		System.out.println();
		bfs(K);

	}

}