DFS, BFS

새로운 마음으로 알고리즘 공부를 다시 시작했다. 기존에는 정리되지 않은 채 마구잡이로 공부했다면 이제 주언어를 java 로 정해서 매일 기록을 남기는 공부를 시작하기 위해 DFS, BFS 를 첫 주제로 잡았다.

DFS 관련 블로그 포스트를 참고해 어떤 문제부터 시작할지 찾아보다가 이미 c++ 로 풀이한 적 있는 1260 번을 다시 풀어봤다.

단순히 풀어서 맞히는 것이 목표가 아닌 java 를 통해 입력 및 출력은 어떤 방식으로 해야할지, 입력받은 그래프 정보는 어떻게 처리할지 등을 고민하며 풀어봤다.

심각한 나의 상태를 확인할 수 있었다! java 로 알고리즘을 풀이한 지 하도 오래 돼서 BufferedReader 와 BufferedWriter 사용법부터 다시 찾아봐야 했다...
또한 한 줄에 여러 입력이 들어올 경우 어떻게 처리해야할지 고민하다가 StringTokenizer 로 처리하는 것이 가장 바람직하다는 글들을 참고하여 STK 를 이용해서 여러 입력을 처리해줬다.

뿐만 아니라 입력 받은 그래프 정보를 인접행렬로 처리할지 LinkedList 로 처리할지조차 금방 결정이 되지 않았다.

1260번과 같이 정점( Vertex ) 의 수가 적을 경우는 인접행렬로 처리하는 게 충분히 가능하다는 것을 확인하고 이번에는 인접행렬로 DFS, BFS 를 모두 해결했다.

매번 DFS, BFS 를 풀 때마다 어떤 방식으로 구현해야할지 항상 찾아봤다. 내 머릿속에 있는 지식이 아닌 구글링을 통해 그때마다 대충 따라치고 넘겼기 때문에 내 지식이 아닌 상태였다.

이번 기회를 통해 확실하게 정리했다.

DFS -> 재귀( Recursion )

BFS -> Queue( While 문 활용 )

아래는 내가 작성한 코드다. 뭔가 정리되지 않은 채 지저분하게 보인다... 이 부분 또한 앞으로 계속 개선해나가야겠지...
어찌 됐든 꾸준함을 목표로 하는 이 여정의 시작을 이 포스팅으로 맞이하게 됐다.

남는 공부를 해보자 해보자!!!

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

public class boj10451 {
    static String input;
    static BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int M;
    static int begin;
    static StringTokenizer st;
    static int map[][];
    static boolean visited[];
    static StringBuilder dfsResult = new StringBuilder();
    static StringBuilder bfsResult = new StringBuilder();

    static void dfs(int begin){
        visited[begin] = true;
        dfsResult.append(Integer.toString(begin) + " ");
        for(int i=1; i<N+1; i++){
            if(map[begin][i]==1 && visited[i]==false){
                dfs(i);
            }
        }
    }

    static void bfs(int begin){
        Queue<Integer> q = new LinkedList<>();
        q.add(begin);
        visited[begin] = true;

        while(!q.isEmpty()){
            int temp = q.poll();
            bfsResult.append(Integer.toString(temp) + " ");

            for(int i=1; i<N+1; i++){
                if(map[temp][i]==1 && visited[i]==false){
                    q.add(i);
                    visited[i] = true;
                }
            }
        }
    }

    public static void main(String args[]) throws IOException {
        st = new StringTokenizer(bfr.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        begin = Integer.parseInt(st.nextToken());

        map = new int[N+1][N+1];
        visited = new boolean[N+1];

        for(int i=0; i<M; i++){
            st = new StringTokenizer(bfr.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x][y] = map[y][x] = 1;
        }

        dfs(begin);
        bfw.write(dfsResult.toString());
        bfw.newLine();

        visited = new boolean[N+1];
        bfs(begin);
        bfw.write(bfsResult.toString());

        bfw.close();
    }
}