[백준] 1260번 : DFS와 BFS(JAVA)

오랜만에 올리는 백준 알고리즘

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

---

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 28단계

 

DFS와 BFS의 카테고리에 포함되어 있는 문제이다.

 

SW마에스트로 코딩테스트 준비를 위해 준비하고 풀어본 문제이다.

 

머리로는 이해가 되지만 코딩하려고하면 잘 안되는 것이 문제이다.

 

DFS와 BFS 카테고리의 문제들을 전부 풀어봐야겠다.

 

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Question_1260 {
	
	static int[][] map;
	static boolean[] visit;
	static int n, m, v;
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		v = sc.nextInt();
		
		map = new int[n+1][n+1];
		visit = new boolean[n+1];
		
		int num1, num2;
		
		for(int i = 1; i <= m; i++) {
			num1 = sc.nextInt();
			num2 = sc.nextInt();
			map[num1][num2] = map[num2][num1] = 1;
		}
		
		dfs(v);
		ResetVisit();
		bfs(v);
	}
	
	public static void ResetVisit() {
		for(int i = 1; i < n+1; i++) {
			visit[i] = false;
		}
		System.out.println();
	}
	
	public static void dfs(int d) {
		visit[d] = true;
		System.out.print(d + " ");
		
		for(int i = 1; i < n + 1; i++) {
			if(map[d][i] == 1 && !visit[i]) {
				dfs(i);
			}
		}
	}
	
	public static void bfs(int b) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(b);
		visit[b] = true;
		
		while(!queue.isEmpty() ) {
			b = queue.poll();
			System.out.print(b + " ");
			
			for(int i = 1; i < n + 1; i++) {
				if(map[b][i] == 1 && !visit[i]) {
					queue.offer(i);
					visit[i] = true;
				}
			}
		}
	}
	
}