[ 백준 ][ 자바 ][ 1260 ] DFS와 BFS

개념잡기엔 좋은 문제 같다.

실패가 뜬 문제길래 봤었는데 파이썬으로 풀다 못풀었던 문제였다.

dfs를 잘 모르는 상황에 

bfs는 2차원 배열에서만 푸는 방법만 익히고 있어서

그래프와 관련된 문제가 나오면 벙벙 하는 상황이었다 (지금)

뭐...제대로 이해를 못하고 있단 얘기겠지

그래서 이번 기회에 한번 풀어봤다

dfs는 일반적으로 재귀로 구현하는 것 같다 

stack도 사용하지만 코드가 컴팩트한 측면에서는 재귀가 훨씬 좋아보인다

문제의 예제에서 나와있는 정점들을 그림으로 그려본후에 

그 다음에 방문할 점을  그려보니 구현이 매우 쉬워졌다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


/*
 * 
4 5 1
1 2
1 3
1 4
2 4
3 4
 */

public class Main_backjoon_1260_dfs_bfs {
	static int[][] MAP = new int[1001][1001];
	static boolean[] visited = new boolean[1001];
	static Queue q = new LinkedList();
	static int N; //정점
	static int M; //간선
	static int V; //시작점
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());
		
		for(int i = 0 ; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			while(st.hasMoreTokens()) {
				 int v1 = Integer.parseInt(st.nextToken());
				 int v2 = Integer.parseInt(st.nextToken());
				 MAP[v1][v2] = 1;
				 MAP[v2][v1] = 1; //양방향
			}
		}
		//printMap();
		dfs(V);
		visited = new boolean[1001];
		System.out.println();
		bfs(V);
	}
	public static void bfs(int v) {
		q.add(v);
		visited[v]  = true;
		
		while(!q.isEmpty()) {
			int p = q.poll();
			System.out.print(p + " ");
			for( int i = 1; i <= N; i++ ) {
				if(MAP[p][i] == 1 && !visited[i]) {
					q.add(i);
					visited[i] = true;
				}
			}
		}

		
	}
	public static void dfs(int v) {
		System.out.print(v + " ");
		visited[v] = true;
		for(int i = 1; i <= N; i++) {
			if(MAP[v][i] == 1  && !visited[i]) {
				dfs(i);
			}
		}
 	}
	public static void printMap() {
		for(int i = 0; i <= N; i++) {
			for (int j =0; j <= N; j++) {
				System.out.print( MAP[i][j] + " ");
			}
			System.out.println();
		}
	}
}