DFS, BFS 복습(스택과 큐)

 오늘은 BFS(큐)복습과 DFS는 재귀가 아닌 스택으로 해보았다.

직관적이면서 쉬운것은 재귀로 푸는것이지만 어느 하나에만 몰두해서 하다보면 스스로를 얽매이는 족쇄가 될것 같아

스택으로 풀려고 노력했다. 결과값은 잘나오는데 백준에서 틀렸다고 나오는 이유는 뭘까..

 

BFS는 그전에 하던 방식 그대로 여서 따로 더 설명할점은 없고 

DFS는 아래와 같이 진행한다. 

 

수정 - 혹은 오름차순으로 방문하고싶을떄는 선입후출의 특징을 이용해 그래프의 뒤부터 방문해도 될듯하다.(BFS의 탐색이 i=0부터 N까지 였으면 DFS는 i=N부터 0까지순으로 하면 가능할듯하다.)

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static int n; //정점개수
    public static int m; //간선개수
    public static int start; //시작점
    public static int[][] graph;
    public static boolean[] visited;
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    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());
        m = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(st.nextToken());

        graph = new int[1001][1001];
        visited = new boolean[10001];
        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();
        bw.write("\n");

        visited = new boolean[1001];

        bfs();
        bw.flush();
        bw.close();

    }

    public static void bfs() throws IOException {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;
        bw.write((int) start + " ");
        while (!queue.isEmpty()) {
            int temp = queue.poll();
            for (int i = 0; i <= n; i++) {
                if (visited[i] == false && graph[temp][i] == 1) {
                    queue.offer(i);
                    visited[i] = true;
                    bw.write((int) i + " ");
                }
            }
        }
    }

    public static void dfs() throws IOException {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        visited[start] = true;
        int pos = start;
        bw.write((int) pos + " ");

        while (!stack.isEmpty()) {
            boolean isConnection = false;

            for (int i = 1; i <= n; i++) {
                if (visited[i] == false && graph[pos][i] == 1) {
                    pos = i;
                    i=1;
                    stack.push(pos);
                    visited[pos] = true;
                    isConnection = true;
                    bw.write((int) pos + " ");
                }
            }

            if (isConnection == false)
                pos = stack.pop();

        }
    }

}