밍의 기록들😉

[문제] 깊이우선탐색과 너비우선탐색 본문

자료구조, 알고리즘/문제풀이

[문제] 깊이우선탐색과 너비우선탐색

민쓰 2018. 9. 9. 21:26

문제




소스코드

import java.util.*;

public class bfsdfs {
	static ArrayList<Integer>[] a;
	static boolean[] check;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String[] input = sc.nextLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int m = Integer.parseInt(input[1]);

		a = (ArrayList<Integer>[]) new ArrayList[n+1];
		for(int i=1; i<=n; i++){
			a[i] = new ArrayList<Integer>();
		}
		for(int i=0; i<m; i++){
			String line = sc.nextLine();
			int u = line.charAt(0)-'@';
			int v = line.charAt(2)-'@';
			a[u].add(v);
			a[v].add(u);
		}
		for(int i=1; i<=n; i++){
			Collections.sort(a[i]);
		}
		int start = sc.next().charAt(0)-'@';
		
		check = new boolean[n+1];
		dfs(start);
		System.out.println();
		
		check = new boolean[n+1];
		bfs(start);
		System.out.println();
	}

	private static void bfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(start);
		check[start] = true;
		while(!q.isEmpty()){
			int x = q.remove(); // head return
			System.out.print((char)(x+'@'));
			for(int y : a[x]){
				if(check[y] == false){
					check[y] = true;
					q.add(y);
				}
			}
		}
	}

	private static void dfs(int x) {
		check[x] = true;
		System.out.print((char)(x+'@'));
		for(int y : a[x]){
			if(check[y] == false){
				dfs(y);
			}
		}
	}
}

풀이


-

'자료구조, 알고리즘 > 문제풀이' 카테고리의 다른 글

[문제] 벽 부수고 이동하기  (0) 2018.09.17
[문제] 미로찾기  (0) 2018.09.14
[문제] 부등호 2529번  (0) 2018.09.05
[문제] 웜바이러스 2606번  (0) 2018.09.05
[문제] 이진 패턴  (0) 2018.09.04
Comments