[GoLang] 백준 1260번, DFS와 BFS

개요

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

1260번: DFS와 BFS

우선 문제 이름처럼 DFS, BFS를 알아야 합니다.

 

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

그래프의 모든 정점을 탐색하는 방법으로

최대한 깊이 탐색을 한 후 더 이상 깊이 들어가지 못한다면 이전으로 돌아와 다른 진행 방향으로 깊이 탐색을 진행합니다.

노드들을 돌며 순서를 스택(재귀)에 쌓는 방식을 사용합니다.

 

아래처럼 끝까지 가보고 안되면 이전 길에서 다른 길을 가보는 방식입니다.

이번 문제에서는 작은 값을 먼저 방문한다로 정의하였기에 작은 값을 먼저 탐색합니다.(이에 맞춰 작은 값을 왼쪽에 둠)

장점

• 찾는 해가 장 좌측에 가까워질수록 빨라진다
• 현재 경로의 노드들만 기억하면 되기에 메모리 사용이 적다

단점

• 해가 없는 깊은 곳에 빠져 시간을 낭비할 수 있다
• 해를 찾는 게 목적일 시 찾은 경로가 최선의 경로인지는 알 수 없다

 

코드

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

type Graph struct {
	adjList map[int][]int // 인접 리스트
	visited map[int]bool  // 참여
	order   []int         // 방문 순서
}

// newGraph : Graph 생성
func newGraph() *Graph {
	g := &Graph{}
	g.adjList = make(map[int][]int)
	g.visited = make(map[int]bool)
	return g
}

// addEdge : Graph에 간선 추가
func (g *Graph) addEdge(from, to int) {
	// 양방향 그래프로 이전 값으로 돌아올 수 있게
	g.adjList[from] = append(g.adjList[from], to)
	g.adjList[to] = append(g.adjList[to], from)
}

// 작은 값을 탐색하기 위해 정렬
func (g *Graph) abjSort() {
	for _, v := range g.adjList {
		sort.Ints(v)
	}
}

// print 함수 추가
func (g *Graph) print() {
	for key, value := range g.order {
		if key == len(g.order)-1 {
			fmt.Printf("%d\n", value)
			break
		}
		fmt.Printf("%d ", value)
	}
}

func (g *Graph) dfs(v int) {
	g.visited[v] = true
	g.order = append(g.order, v)

	for _, i := range g.adjList[v] {
		// 인접 리스트 방문(dfs)을 재귀로 반복
		// 방문하지 않은 노드만 방문, bool의 기본 값은 false
		if !g.visited[i] {
			g.dfs(i)
		}
	}
}

func main() {
	reader := bufio.NewReader(os.Stdin)

	// 정점의 수, 간선의 수, 시작 정점
	// 그림에서는 이해를 위해 시작점이 고정된 것 처럼 그렸으나 실제로는 시작점은 없다.
	var n, m, v int
	fmt.Fscanln(reader, &n, &m, &v)

	// Graph 생성
	g := newGraph()

	for i := 0; i < m; i++ {
		var from, to int
		// 간선의 개수만큼 입력 받기
		fmt.Fscanln(reader, &from, &to)
		// 간선은 양방향이므로 양쪽에 모두 추가
		g.addEdge(from, to)
	}
	g.abjSort()

	g.dfs(v)
	g.print()
}

 

그래프 구조체 생성 함수와 addEdge, dfs 등을 메서드로 만들었습니다.

코드의 논리 순서는 아래와 같습니다.

• 그래프 생성
• 반복문을 돌며 Key, Value 형태로 시작과 끝이 명확한 간선을 생성
• dfs에서 시작 간선을 기준으로 연결된 노드들을 탐색 (addEdge에서 이미 크기순으로 정렬)
  • 다음과 같이 abjList에 적재됩니다.

map[1:[2 3 4] 2:[1 4] 3:[1 4] 4:[1 2 3]]

• 재귀 함수로 탐색하면서 순서를 order에 저장

 

스택

이미지 출처 :  https://www.programiz.com/dsa/stack

위에서 재귀로 함수를 돌렸습니다.

재귀는 특성상 가장 최근의 한 함수부터 결괏값을 리턴하는데 이 형태 LIFO인 Stack과 같습니다.

 

 

BFS(Breadth First Search), 너비 우선 탐색

한쪽을 깊이 파던 DFS와 다르게 루트를 기준으로 한 단계 아래를 다 탐색한 후

한 단계 기준으로 두 단계 깊이의 노드들을 다 탐색하는 방법입니다.

장점

• 찾는 해가 깊이가 낮을수록 빨라진다
• 운이 좋다면 바로 찾을 수 있다.

단점

• 해를 찾는 게 목적이라면 최선의 경우의 수를 알 수 있다.
• 최악의 경우 가장 오래 걸릴 수 있다.

 

코드

...

// 초기화 함수 추가
func (g *Graph) init() {
	g.order = []int{}
	for i := 0; i < len(g.visited); i++ {
		g.visited[i] = false
	}
}

// bfs 함수 추가
func (g *Graph) bfs(v int) {
	queue := []int{v}
	g.visited[v] = true

	// 큐가 빌 때 까지 반복
	for len(queue) > 0 {
		// 큐에는 깊이가 낮은 값 부터 차례대로 들어가고
		// 깊이가 낮은 걸 방문을 다 해야 다음 깊이로 넘어가짐
		currentVertex := queue[0]
		queue = queue[1:]
		g.order = append(g.order, currentVertex)

		// 반복문 안에서 계속 큐에 값을 추가해줌
		for _, neighbor := range g.adjList[currentVertex] {
			// 방문하지 않은 인접된 노드들을 큐에 추가
			if !g.visited[neighbor] {
				g.visited[neighbor] = true
				queue = append(queue, neighbor)
			}

		}
	}
}

func main() {
	reader := bufio.NewReader(os.Stdin)

	// 정점의 수, 간선의 수, 시작 정점
	// 그림에서는 이해를 위해 시작점이 고정된 것 처럼 그렸으나 실제로는 시작점은 없다.
	var n, m, v int
	fmt.Fscanln(reader, &n, &m, &v)

	// Graph 생성
	g := newGraph()

	for i := 0; i < m; i++ {
		var from, to int
		// 간선의 개수만큼 입력 받기
		fmt.Fscanln(reader, &from, &to)
		// 간선은 양방향이므로 양쪽에 모두 추가
		g.addEdge(from, to)
	}
	g.abjSort()

	g.dfs(v)
	g.print()
    
    // 코드 추가
	g.init()
	g.bfs(v)
	g.print()
}

 

나머지는 다 똑같지만 bfs는 재귀가 아니고 반복문인데 조건의 체크 값을 계속 추가해 줍니다.

큐로 먼저 입력된 값을 먼저 사용하게 하는 데 여기서는

깊이 낮은 값을 먼저 큐에 넣은 후 차례대로 반복문을 통해 그와 인접된 노드를 넣습니다.

 

큐

위에서 말했듯이 깊이가 낮은 순서대로 큐에 넣고 먼저 넣은 순서대로 이를 빼냅니다.

그 방식으로 위는 너비 우선 방식을 할 수 있게 되는 것이죠

이미지 출처 : https://www.programiz.com/dsa/queue