[백준] DFS와 BFS

백준 1260. DFS와 BFS

백준 1260번 링크

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

/* 인접행렬 그래프 클래스
 * nV: 정점. Vertex의 개수
 * nE: 간선. Edge의 개수
 */
class AdjGraph{
	private int nV;
	private int[][] graph;
	private boolean[] hasVisited;
	
	//생성자
	public AdjGraph(int nV) {
		//멤버변수 초기화
		this.nV = nV;
		this.graph = new int[nV+1][nV+1];
		this.hasVisited = new boolean[nV+1];
	}
	
	//양방향 간선 추가
	public void add(int x, int y) {
		graph[x][y] = 1;
		graph[y][x] = 1;
	}
	
	//단방향 간선 추가
	public void addSingle(int x, int y) {
		graph[x][y] = 1;
	}
	
	
	//visited 초기화
	public void clear() {
		for(int i=1; i<=nV; i++) {
			hasVisited[i] = false;
		}
	}
	
	//인접행렬 출력
	public void print() {
		System.out.println("= 인접행렬 출력 =");
        for(int i=0; i<graph.length; i++) {
            for(int j=0; j<graph[i].length; j++)
                System.out.print(graph[i][j] + " ");
            System.out.println();
        }
	}
	
	//DFS Logic
	public void dfs(int idx) {
		//dfs()에 들어온 정점을 방문처리한다.
		hasVisited[idx] = true;
		System.out.print(idx + " ");
		
		/*
		 * i가 1부터 끝까지 돌며 자신과 연결된 정점을 찾음.
		 * 정점을 찾았다면 잠시 함수를 멈추고 다음 dfs(i)를 실행했다가 처리가 모두 완료되면 돌아옴.
		 * 따라서 깊이우선탐색이 가능함.
		 */
		for(int i=1; i<=nV; i++) {
			//연결이 되어있고 해당 정점이 미방문일경우.
            if(graph[idx][i] == 1 && hasVisited[i] == false)
            	dfs(i);
		}
	}
	
	//BFS Logic
	public void bfs(int idx) {
		Queue<Integer> queue = new LinkedList<>();
		
		// queue에 시작 정점 추가.
		queue.add(idx);
		hasVisited[idx] = true;
		
		while( !queue.isEmpty() ) {
			// poll: pop하고 pop된 값 반환
			idx = queue.poll();
			System.out.print(idx + " ");
			
			for(int i=1; i<=nV; i++) {
				if (graph[idx][i] == 1 && hasVisited[i] == false) {
					//queue에 인접 정점 삽입
					queue.add(i);
					//방문처리
					hasVisited[i] = true;
				}
			}
			
		}
	}
	
}


// Main이 있는 클래스
public class Main {
	//멤버변수
	int nV;
	int nE;
	AdjGraph graph;
	
	//생성자
	public Main() {
		Scanner sc = new Scanner(System.in);
		//정점의 개수 받기
		nV = sc.nextInt();
		//간선의 개수 받기
		nE = sc.nextInt();
		int n = sc.nextInt();
		//그래프 초기화
		graph = new AdjGraph(nV);
		
		//graph에 간선 추가하기.
		for(int i=0; i<nE; i++)
			graph.add(sc.nextInt(), sc.nextInt());
		
		//DFS로 출력
		graph.dfs(n);
		System.out.println();
		
		//BFS로 출력. clear로 visited 초기화
		graph.clear();
		graph.bfs(n);
		
		sc.close();
	}
	
	//메인 메서드
	public static void main(String[] args) {
		Main mm = new Main();
	}
}