Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

24. DFS와 BFS

그래프를 순회하는 알고리즘을 배워 봅시다.

Java / Python

1. DFS와 BFS

1260번

DFS와 BFS를 다루는 문제

이번 문제는 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하는 문제입니다. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료해야 합니다.

DFS(Depth-First Search) : 깊이 우선 탐색

• 재귀나 스택으로 구현
• 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

BFS(Breath-First Search) : 너비 우선 탐색

• 큐로 구현 (FIFO원칙으로 탐색)
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

• Java

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

public class Main {
	static int[][] arr;	
	static boolean[] check;
	static StringBuilder sb = new StringBuilder();
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
		StringTokenizer st = new StringTokenizer(br.readLine());           
		int N = Integer.parseInt(st.nextToken());	// 정점 개수
		int M = Integer.parseInt(st.nextToken());	// 간선 개수       
		int V = Integer.parseInt(st.nextToken());	// 탐색을 시작할 정점의 번호
        
		arr = new int[N + 1][N + 1];      
		check = new boolean[N + 1];
        
		// 노드 , 간선 값 초기화
		for(int i = 0; i < M; i++){
			st = new StringTokenizer(br.readLine()); 
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			arr[s][e] = 1;
			arr[e][s] = 1;
		}
        
		dfs(V);
		sb.append("\n");
		bfs(V);
        
		bw.write(sb + "\n");

		bw.flush();
		bw.close();
		br.close();
	}
	public static void initC(){
		for(int i = 0 ; i < check.length; i++) check[i] = false;
	}
	public static void dfs(int st) {
		sb.append(st + " ");
		check[st] = true;
        
		for (int i = 1; i < check.length; i++) {
			if (i != st && !check[i] && arr[st][i] == 1)
				dfs(i);
        }
    }
	public static void bfs(int st){
		initC();
        
		Queue<Integer> queue = new LinkedList<Integer>(); 
		
		queue.add(st);
		check[st] = true;
		
		while(!queue.isEmpty()) {		
			int temp = queue.poll();
			sb.append(temp + " ");
			for(int i = 1; i < check.length;i++) {
				if(i != temp && !check[i] && arr[temp][i] == 1) {
					queue.add(i);
					check[i] = true;
				}
			}
		}
		sb.append("\n");
	}
}

• Python

import sys
N, M, V = map(int, sys.stdin.readline().split())
arr = [[0]*(N+1) for _ in range(N + 1)]
check = [0 for _ in range(N + 1)]

def dfs(v):
    print(v, end=' ')
    check[v] = 1
    for i in range(1, N + 1):
        if check[i] == 0 and arr[v][i] == 1:
            dfs(i)

def bfs(v):
    queue = [v]
    check[v] = 0
    while(queue):
        v = queue[0]
        print(v, end=' ')
        del queue[0]
        for i in range(1, N + 1):
            if check[i] == 1 and arr[v][i] == 1:
                queue.append(i)
                check[i] = 0

for i in range(M):
    s, e = map(int, sys.stdin.readline().split())
    arr[s][e] = 1
    arr[e][s] = 1
    
dfs(V)
print()
bfs(V)