2022.06.24 백준 Q1260

학습 내용 : 스택 큐를 이용한 자료구조 만들기. DFS,BFS 처리 방법

이 문제는 DFS, BFS를 구현하는 문제이다.

DFS는 깊이 우선 탐색으로 그래프에서 깊이를 하나씩 늘려가면서 내려가다가 더 이상 인접 노드가 나오지 않으면 한 칸 위로 올라가는 구조이다. 이를 구현하기 위해서는 다시 한 칸 위로 올라가는 것이 스택을 톻해 pop하는 것도 같으므로 stack을 이용해 구현했다. 해당 노드가 스택에 들어갔었던 노드인지 확인하기 위해 isvisited boolean 변수 배열을 사용했다. 처음에는 무조건적으로 currentVertex에 있는 값을 출력에 넣어줘야 할 줄 알았는데 다시 되돌아올때 이전에 넣었던 값도 다시 currentVertex가 될 수 있어 isVisited가 false일때만 출력에 넣어주게 설정하였다. 또 currentNode에서 모든 노드를 돌았을 때 근처에 방문하지 않은 노드가 없으면 pop을 하고 currentNode를 첫번째 stack값으로 설정한다.

 

 

BFS는 넓이우선탐색으로 currentNode와 관련된 모든 노드를 출력하고 다음 깊이로 내려가 다시 같은 작업을 수행한다. 따라서 Queue로 자료를 구성하는게 좋다. currentNode에서 인접 노드 중 방문하지 않은 점들을 모두 Queue에 넣고 한바퀴 돌면 한 Vertex를 poll하고 다음 Vertex로 넘어간다. 

 

 

 

-코드 본문-

package BaekJoon1260;

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

public class Main {
    static boolean [][] table;
    static int vertex, edge,startingVertex ;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String s = bf.readLine();
        StringTokenizer st = new StringTokenizer(s);
        vertex = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());
        startingVertex = Integer.parseInt(st.nextToken());
        table = new boolean[vertex][vertex];
        for(int i=0;i<edge;i++){
            s=bf.readLine();
            st = new StringTokenizer(s);
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            table[a-1][b-1]=true;
            table[b-1][a-1]=true;
        }
        DFS();
        BFS();
    }
    static void DFS(){
        boolean [] isVisited = new boolean[vertex];
        Stack<Integer> stack = new Stack<>();
        int currentVertex = startingVertex;
        stack.push(currentVertex);
        StringBuilder sb = new StringBuilder();
        boolean haveVertex;
        while(true){
            if(stack.isEmpty()){
                System.out.println(sb.toString().trim());
                break;
            }
            if(!isVisited[currentVertex-1]) sb.append(currentVertex).append(" ");
            isVisited[currentVertex-1]=true;
            haveVertex = false;
            for(int i=0;i<vertex;i++){
                if(!isVisited[i]&&table[currentVertex-1][i]){
                    haveVertex=true;
                    stack.push(i+1);
                    currentVertex = i+1;
                    break;
                }
            }
            if(!haveVertex){
                stack.pop();
                if(stack.isEmpty()) continue;
                currentVertex = stack.peek();
            }

        }
    }
    static void BFS(){
        boolean [] isVisited = new boolean[vertex];
        Queue<Integer> queue = new LinkedList<>();
        int currentVertex = startingVertex;
        queue.offer(currentVertex);
        isVisited[currentVertex-1]=true;
        StringBuilder sb = new StringBuilder();
        while(true){
            if(queue.isEmpty()) {
                System.out.println(sb.toString().trim());
                break;
            }
            currentVertex = queue.peek();
            sb.append(currentVertex).append(" ");
            for(int i=0;i<vertex;i++){
                if(!isVisited[i]&&table[currentVertex-1][i]){
                    isVisited[i]=true;
                    queue.offer(i+1);
                }
            }
            queue.poll();
        }
    }
}