[DFS] 백준 DFS와 BFS 1260번

[DFS] 백준 DFS와 BFS 1260번

---

문제 설명

그래프로 DFS로 탐색한 결과와

BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.

단, 방문할 수 있는 정점이 여러 개인 경우에는

정점 번호가 작은 것을 먼저 방문하고,

더 이상 방문할 수 있는 점이 없는 경우 종료한다.

정점 번호는 1번부터 N까지이다.

 

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000),

간선의 개수 M(1 ≤ M ≤ 10,000),

탐색을 시작할 정점의 번호 V가 주어진다.

다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.

어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다.

입력으로 주어지는 간선은 양방향이다.

---

출력

첫째 줄에 DFS를 수행한 결과를,

그 다음 줄에는 BFS를 수행한 결과를 출력한다.

V부터 방문된 점을 순서대로 출력하면 된다.

 

** 풀이 방법

 

DFS (깊이 우선 탐색)

BFS (너비 우선 탐색)

 

인접 노드를 담을 ArrayList와

탐색 여부를 파악할 boolean 배열을 선언한다.

static ArrayList<Integer>[] A; 
static boolean[] visited;

 

N, M, Start를 입력받는다.

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());

int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int Start = Integer.parseInt(st.nextToken());

 

N+1 크기의 ArrayList를 생성해서

M개 만큼 인접한 노드를 입력받은 후

ArrayList에 저장시킨다.

A = new ArrayList[N+1];
for (int i=1; i<N+1; i++) {
    A[i] = new ArrayList<Integer>();
}
for (int i=1; i<M+1; i++) {
    st = new StringTokenizer(bf.readLine());
    int S = Integer.parseInt(st.nextToken());
    int V = Integer.parseInt(st.nextToken());
    A[S].add(V); A[V].add(S);
}

 

정점 번호가 작은 것부터 시작해야 하기 때문에모든 ArrayList들을 오름차순으로 정렬시킨다.

for (int i=1; i<N+1; i++) {
    Collections.sort(A[i]);
}

 

탐색 여부를 파악할 boolean 배열도 초기화한다.그리고 DFS, BFS 각각매개변수에 시작할 정점을 넣어서탐색 함수를 호출한다.

visited = new boolean[N+1];
DFS(Start);
System.out.println(); //DFS 한 줄 띄고 BFS 출력할 것이기 때문
visited = new boolean[N+1];
BFS(Start);

 DFS 탐색 함수

public static void DFS(int now_node) {
    System.out.print(now_node + " "); // 현재 노드를 공백과 함께 출력 + 탐색 순서대로 나열할 것이므로 print!
    visited[now_node] = true; // 탐색 상태를 true로 바꿈
    for (int i : A[now_node]) { // 현재 노드의 인접 노드에 접근해서
        if (visited[i]==false) // 탐색 상태가 false이면
            DFS(i); // 재귀적으로 DFS 함수 다시 호출
    }
}

 

BFS 탐색 함수

public static void BFS(int now_node) {
    Queue<Integer> que = new LinkedList<Integer>();
    que.add(now_node); // 큐에 현재 노드를 삽입 
    visited[now_node] = true; // 방문한 것으로 바꿈
    while (!que.isEmpty()) { // 큐가 빈 상태일 때까지 반복
        int i = que.poll(); // 큐는 FIFO이므로 젤 앞에 있는 것을 삭제 
        System.out.print(i + " "); // 꺼낸 원소를 순서대로 출력
        for (int a : A[i]) { // 인접 노드들에 접근해서
            if (!visited[a]) { // 상태가 false이면
                que.add(a); // 큐에 삽입
                visited[a] = true; // 방문한 것으로 바꿈 
            }
        }
    }
}

 

<> 전체 코드 </>

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

class Main {
    static ArrayList<Integer>[] A; 
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int Start = Integer.parseInt(st.nextToken());
        A = new ArrayList[N+1];
        for (int i=1; i<N+1; i++) {
        	A[i] = new ArrayList<Integer>();
        }
        for (int i=1; i<M+1; i++) {
        	st = new StringTokenizer(bf.readLine());
        	int S = Integer.parseInt(st.nextToken());
        	int V = Integer.parseInt(st.nextToken());
        	A[S].add(V); A[V].add(S);
        }
        for (int i=1; i<N+1; i++) {
        	Collections.sort(A[i]);
        }
        visited = new boolean[N+1];
        DFS(Start);
        System.out.println();
        visited = new boolean[N+1];
        BFS(Start);
        
    }
    
    public static void DFS(int now_node) {
    	System.out.print(now_node + " ");
        visited[now_node] = true;
        for (int i : A[now_node]) {
            if (visited[i]==false)
                DFS(i);
        }
    }
    public static void BFS(int now_node) {
    	Queue<Integer> que = new LinkedList<Integer>();
    	que.add(now_node);
    	visited[now_node] = true;
    	while (!que.isEmpty()) {
    		int i = que.poll();
    		System.out.print(i + " ");
    		for (int a : A[i]) {
    			if (!visited[a]) {
    				que.add(a);
    				visited[a] = true;
    			}
			}
    	}
    }
}