[Java] 백준 1260번 문제 (DFS와 BFS)

문제설명

 

소스코드

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

public class Main
{
   static int N; //vertex
   static int M; //edge
   static int V; //첫 탐색
   static boolean visited[]; //방문 표시
   static int vertex[][]; //인접 행렬
   static StringBuilder sb = new StringBuilder();
   
   static void DFS(int V) //첫 탐색 위치를 매개변수로 받음
   {
	   Stack<Integer> stack = new Stack<>();
	   visited = new boolean[N + 1]; //(인덱스는 0부터 시작이므로 편의상 1추가)
	   stack.push(V);
	   while(!stack.empty()) //스택이 비어있지 않다면
	   {
		   int temp = stack.pop(); //스택에서 pop한 것을 임시로 저장
		   if(visited[temp] == true) continue; //이미 방문한 곳이라면 pass
		   else //방문한 곳이 아니라면
		   {
			   sb.append(temp + " "); //출력
			   visited[temp] = true; //방문했다고 표시
			   for(int j = vertex[temp].length - 1; j > 0; --j) //해당 행에 있는 모든 vertex를 검사, vertex가 작은 수부터 방문해야하므로 역순으로 루프
			   {
				   if(vertex[temp][j] == 1) stack.push(j); //두 노드가 간선으로 연결되어 있다면 스택에 push
			   }
		   }
	   }
	   System.out.println(sb.toString());
   }
   
   static void BFS(int V) //첫 탐색 위치를 매개변수로 받음
   {
	   Queue<Integer> queue = new LinkedList<>();
	   visited = new boolean[N + 1]; //(인덱스는 0부터 시작이므로 편의상 1추가)
	   queue.offer(V);
	   while(!queue.isEmpty()) //큐가 비어있지 않다면
	   {
		   int temp = queue.poll(); //큐에서 dequeue 한 것을 임시로 저장
		   if(visited[temp] == true) continue; //이미 방문한 곳이라면 pass
		   else //방문한 곳이 아니라면
		   {
			   sb.append(temp + " "); //출력
			   visited[temp] = true; //방문했다고 표시
			   for(int j = 1; j < vertex[temp].length; ++j) //해당 행에 있는 모든 vertex를 검사
			   {
				   if(vertex[temp][j] == 1) queue.offer(j); //두 노드가 간선으로 연결되어 있다면 큐에 enqueue
			   }
		   }
	   }
	   System.out.println(sb.toString());
   }
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); //vertex 수(정점 수)
		M = Integer.parseInt(st.nextToken()); //edge 수(간선 수)
		V = Integer.parseInt(st.nextToken()); //첫 탐색을 어디로 하는지 
		vertex = new int[N + 1][N + 1]; //인접 행렬 (인덱스는 0부터 시작이므로 편의상 1추가)
		for(int i = 1; i <= M; ++i) //간선의 수 만큼 입력을 받음
		{
			st = new StringTokenizer(br.readLine());
			int row = Integer.parseInt(st.nextToken());
			int col = Integer.parseInt(st.nextToken());
			vertex[row][col] = 1; //무방향 그래프는 대칭 행렬이므로
			vertex[col][row] = 1; //무방향 그래프는 대칭 행렬이므로
		}
		DFS(V);
		sb = new StringBuilder(); //StringBuilder 초기화
		BFS(V);
	}
}

 

설명

• DFS는 스택(LIFO)으로 구현
• BFS는 큐(FIFO)로 구현
• 자세한 설명은 주석 참고