📍 1. 문제

📍 2. 풀이

DFS와 BFS의 가장 기초가 되는 문제인듯.

📌 대부분의 DFS와 BFS문제의 풀이 흐름과 유형은 다음과 같다.

1. 그래프를 생성한다. 그래프 생성 방법엔 3가지 정도가 있다.

• (1) 인접행렬
• (2) 인접리스트
• (3) 자바 클래스

2. 그래프를 순회한다. 순회 방법엔 3가지가 있다.

• (1) BFS - QUEUE
• (2) DFS - Recursive
• (3) DFS - Stack

DFS와 BFS문제의 유형은 위와 비슷하다.
인접행렬, 인접리스트는 각각 구현 방법에 따라 장단점이 존재하며,
BFS와 DFS 어느 방법으로 순회하냐에 따라 장단점도 존재한다.
자바클래스는 LeetCode에 주로 나온다.

📍 3. 코드

숫자가 작은것 부터 연산해야한다는 조건이 있다.
예를들어 스택안에 2, 3, 4가 들어가야한다면, 2부터 연산해야한다.
따라서 stack연산시 배열을 반대로 연산하거나,
peek, flag를 적절히 사용해야한다.
안하는방법은 모르겠다. 백준문제는 이렇게 해야만 했다..

1. 인접행렬 + Dfs-Stack + DFS-Recursive + Bfs-Queue
   stack에서 for문 역순으로.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        //input : vertex , edge , start
        int vertex = Integer.parseInt(st.nextToken());
        int edge = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        //인접행렬
        int[][] map = new int[vertex + 1][vertex + 1];
        boolean[] visited = new boolean[vertex + 1];

        //edge set
        for(int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            map[v1][v2] = 1;
            map[v2][v1] = 1;
        }
        dfsStack(start, map, visited);
        System.out.println();
        Arrays.fill(visited, false);
//        dfsRecursive(start, map, visited);
//        System.out.println();
//        Arrays.fill(visited, false);
        bfsQueue(start, map, visited);

    }
    public static void dfsStack(int vertex, int[][] map, boolean[] visited) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(vertex);

        while(!stack.isEmpty()) {
            vertex = stack.pop();
            if(!visited[vertex]) {
                visited[vertex] = true;
                System.out.print(vertex + " ");
                for(int i = map[vertex].length - 1; i >= 1; i--) {
                    if(map[vertex][i] == 1 && !visited[i] ) {
                        stack.push(i);
                    }
                }
            }
        }
    }

    public static void dfsRecursive(int vertex, int[][] map, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " ");
        for(int i = 1; i < map[vertex].length; i++) {
            if(map[vertex][i] == 1 && visited[i] == false) {
                dfsRecursive(i, map, visited);
            }
        }
    }
    public static void bfsQueue(int vertex, int[][] map, boolean[] visited) {
        Queue<Integer> que = new LinkedList<>();
        que.add(vertex);
        visited[vertex] = true;

        while(!que.isEmpty()) {
            vertex = que.poll();
            System.out.printf(vertex + " ");

            for(int i = 1; i < map[vertex].length; i++) {
                if (map[vertex][i] == 1 && !visited[i]) {
                    que.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

2. 인접리스트 + Dfs-Stack + DFS-Recursive + Bfs-Queue

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int vertex = Integer.parseInt(st.nextToken());
		int edge = Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(st.nextToken());
		
		boolean[] visited = new boolean[vertex + 1];
		ArrayList<Integer>[] list = new ArrayList[vertex + 1];
		for(int i = 0; i < list.length; i++) {
			list[i] = new ArrayList<Integer>();
		}
		
		for(int i = 0; i < edge; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			
			list[v1].add(v2);
			list[v2].add(v1);
		}
		for(int i = 0; i < list.length; i++) {
			Collections.sort(list[i]);
		}
		
//		dfsStack(start, list, visited);
//		System.out.println();
//		Arrays.fill(visited, false);
		dfsRecursive(start, list, visited);
		System.out.println();
		Arrays.fill(visited, false);
		bfsQueue(start, list, visited);
	}
	
	public static void dfsStack(int start, ArrayList<Integer>[] list, boolean[] visited) {
		Stack<Integer> stack = new Stack<>();
		stack.push(start);
		
		while(!stack.isEmpty()) {
			int v = stack.pop();
			if(visited[v] == false) {
				visited[v] = true;
				System.out.print(v + " ");
				for(int i = list[v].size() - 1; i >= 0; i-- ) {
					if(visited[list[v].get(i)] == false) {
						stack.push(list[v].get(i));						
					}
				}
			}
		}
	}
	
	public static void dfsRecursive(int vertex, ArrayList<Integer>[] list, boolean[] visited) {
		visited[vertex] = true;
		System.out.print(vertex + " ");
		
		for(int i = 0; i < list[vertex].size(); i++) {
			if(visited[list[vertex].get(i)] == false) {
				dfsRecursive(list[vertex].get(i), list, visited);
			}
		}
	}
	
	
	public static void bfsQueue(int start, ArrayList<Integer>[] list, boolean[] visited) {
		Queue<Integer> que = new LinkedList<>();
		que.add(start);
		
		while(!que.isEmpty()) {
			int v = que.poll();
			if(visited[v] == false) {
				visited[v] = true;
				System.out.print( v + " ");
				for(int vertex : list[v]) {
					if(visited[vertex] == false) {
						que.add(vertex);
					}
				}
			}
		}
		
	}

}