[백준 1260] DFS와 BFS (Java) - DFS,BFS

[문제링크]

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

1260번: DFS와 BFS

[풀이 소스]

package algorithm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class DfsBfs1260 {
    public static int nodeCount;
    public static LinkedList<Integer>[] nearNodeList;
    
    
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        
        nodeCount=Integer.parseInt(st.nextToken());
        int EdgeCount=Integer.parseInt(st.nextToken());
        int startNode=Integer.parseInt(st.nextToken());
        
        // 인접노드배열 선언
        nearNodeList=new LinkedList[nodeCount+1];
        for(int i=0; i<=nodeCount;i++) {
            nearNodeList[i]=new LinkedList<Integer>();
        }
        
        // 입력받아 인접노드배열구성
        while(EdgeCount-->0) {
            st= new StringTokenizer(br.readLine());
            int node1=Integer.parseInt(st.nextToken());
            int node2=Integer.parseInt(st.nextToken());
            
            // 인접노드배열에 추가하여 정리
            nearNodeList[node1].add(node2);
            nearNodeList[node2].add(node1);
            Collections.sort(nearNodeList[node1]);
            Collections.sort(nearNodeList[node2]);
        }
        
        // 답을 위한 sb선언
        StringBuilder dfsWay=new StringBuilder();
        StringBuilder bfsWay=new StringBuilder();
        
        // 방문여부를 체크하는 boolean배열
        boolean[] dfsVisited=new boolean[nodeCount+1];
        boolean[] bfsVisited=new boolean[nodeCount+1];
        
        dfs(startNode, dfsVisited, dfsWay);
        bfs(startNode, bfsVisited, bfsWay);
        
        System.out.println(dfsWay+"\n"+bfsWay);
    }
    
    // DFS : Stack이용 or "재귀함수"
    public static void dfs(int startNode, boolean[] visited, StringBuilder way) {
        // 시작노드(해당노드)의 방문여부 체크 >> 방문시 종료
        if(visited[startNode]) return;
        
        // 미방문시 >> 방문 체크 후 순서로 기록
        visited[startNode]=true;
        way.append(startNode+" "); 
        
        // 자식노드 탐색(반복) >> 재귀함수
        for(int nextNode:nearNodeList[startNode]) {
            dfs(nextNode, visited, way);
        }
    }
    
    // BFS : Queue이용
    public static void bfs(int startNode, boolean[] visited, StringBuilder way) {
        Queue<Integer> queue=new LinkedList<Integer>();
        
        // 시작노드 큐에 삽입
        queue.offer(startNode);
        
        while(!queue.isEmpty()) {
            // 탐색할 노드를 pop!
            startNode=queue.poll();
            
            // 탐색노드의 방문여부 확인
            //  => 방문 : 넘어가기
            if(visited[startNode]) continue;
            //  => 미방문 : 방문 체크 후 방문기록
            visited[startNode]= true;
            way.append(startNode+" ");
            //            : 해당 자식을 큐에 모두 삽입
            for (int nextNode:nearNodeList[startNode]) {
                queue.offer(nextNode);
            }
            
        }
        
    }
 
}
 

     

 

[느낀점]

    - DFS : 재귀함수 or Stack 사용

    - BFS : Queue 사용, 재귀동작사용X!!