[백준] 1260 : DFS와 BFS JAVA 풀이

 

인접행렬 방식으로 풀었다.

 

import java.io.*;
import java.util.*;
public class Main {
	// 인접행렬 생성
	static int[][] graph;
    // 방문했는지 확인하기 위한 행렬
	static boolean[] visit;
    // 정점의 개수
	static int N;
	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());
        // 간선의 개수
		int M = Integer.parseInt(st.nextToken());
        // 시작 정점
		int V = Integer.parseInt(st.nextToken());
		
        // [정점의 개수+1][정점의 개수+1]
		graph = new int[N+1][N+1];
		visit = new boolean[N+1];
		
        // 인접행렬에 간선 체크
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			graph[x][y] = 1;
			graph[y][x] = 1;
		}
		
     	
		dfs(V);
		System.out.println();
		
        // dfs 수행 뒤 방문한 정점을 다시 초기화
		for(int i=0;i<visit.length;i++)visit[i] = false;
		
		bfs(V);
	}
	
	public static void dfs(int v) {
    	// 정점을 방문했다고 체크
		visit[v] = true;
        // 방문한 정점 출력
		System.out.print(v+" ");
		
		for(int i=1;i<N+1;i++) {
        	// 인접 정점 중 아직 미방문인 정점에 대해 dfs 재귀호출
			if(graph[v][i]==1&&visit[i]==false) {
				dfs(i);
			}
		}
	}
	
  
	public static void bfs(int v) {
    	// 큐 생성
		Queue<Integer> q = new LinkedList<>();
        // 정점을 큐에 추가
		q.offer(v);
        // 정점을 방문했다고 체크
		visit[v] = true;
		
        // 큐가 빌 때까지 반복
		while(!q.isEmpty()) {
        	// 큐에서 수 하나를 제거
			int tmp = q.poll();
            // 출력
			System.out.print(tmp+" ");
			
            // 큐에서 제거한 정점의 인접 정점을 큐에 넣고 방문했다고 체크
			for(int i=1;i<N+1;i++) {
				if(graph[tmp][i]==1&&visit[i]==false) {
					q.offer(i);
					visit[i] = true;
				}
			}
		}
	}
 
}