지구정복

[BFS,DFS] 백준 - DFS와 BFS 본문

데이터 엔지니어링 정복/Algorithm

[BFS,DFS] 백준 - DFS와 BFS

eeaarrtthh 2021. 6. 25. 14:26
728x90
반응형

-문제

https://www.acmicpc.net/problem/1260

 

 

-자바

package bfs_dfs;

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

public class BJ1260 {
    static int n,m,v;
    static int[][] map;
    static boolean[] visit;
    static StringBuffer sb = new StringBuffer();

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

        //각 노드에서 갈 수 있는 모든 노드를 표시하기 위해
        //2차원배열로 행렬을 만든다.
        map = new int[n+1][n+1];
        visit = new boolean[n+1];
        for( int i=1; i<=m; i++ ) {
            st = new StringTokenizer( br.readLine() );
            int a = Integer.parseInt( st.nextToken() );
            int b = Integer.parseInt( st.nextToken() );

            //a노드에서 b노드 갈 수 있음 == b노드에서 a노드 갈 수 있음
            //이를 표현하기 위해 배열의 인덱스를 노드,
            //'갈 수 있음'을 1로 표현한다.
            map[a][b] = map[b][a] = 1;
        }

        dfs( v );
        sb.append( "\n" );
        visit = new boolean[n+1];

        bfs( v );

        System.out.println( sb );
    }

    static void dfs( int start ) {
        sb.append( start+" " );
        visit[start] = true;
        
        for( int i=1; i<=n; i++ ) {
            if( map[start][i] == 1 && visit[i] == false ) {
                dfs( i );
            }
        }
    }

    static void bfs( int start ) {
        sb.append( start+" " );
        visit[start] = true;

        Queue<Integer> que = new LinkedList<Integer>();
        que.add( start );

        while( !que.isEmpty() ) {
            int cur_val = que.poll();

            for( int i=1; i<=n; i++ ) {
                if( map[cur_val][i] == 1 && visit[i] == false ) {
                    sb.append( i + " " );
                    visit[i] = true;
                    que.add( i );
                }
            }
        }
    }
}
728x90
반응형
Comments