[알고리즘] BFS - 너비 우선 탐색이란?

Intro.

안녕하세요 Pu드로이드 입니다^^

 

취업차.. 코딩테스트 준비를 위해 1일 1백준 알고리즘 풀이를 꾸준히 하고 있는데요!

 

더 나은 문제 접근을 위해 유튜브 바킹독님의 영상으로 알고리즘 기본기를 다질 계획이며,

 

동시에 블로그 포스팅을 통해 정보를 기록하고 공유하려 합니다! 

 

궁금한 점 질문, (정중한)조언을 매우 매우 환영하니 부담 없이 댓글 부탁드려요!

 

 

---

 

BFS

너비 우선 탐색 - Breadth First Search

 

너비 우선 탐색은 그래프 탐색 방법중 하나로,

그림과 같이 중심으로부터 가장 가까운곳을 우선적으로 탐색하는 알고리즘입니다!

 

그림의 숫자를 보면 1을 중심으로 주변부터 탐색하는것을 확인할 수 있는데요,

이를 구현하기 위해 보통 큐를 사용합니다.

 

FIFO 이라는 큐의 특성을 사용하여 

중심으로부터 가까운 곳의 정보를 큐에 넣고

차근차근 Pop 하며 문제를 해결한다고 이해하시면 됩니다!

 

대표적인 문제는 다음과같이 미로 탐색입니다ㅎㅎ

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

2178번: 미로 탐색

 

 

 

<풀이과정>

fun main(){
    // 시작 위치와 도착 위치도 개수 포함
    // bfs 풀이
    val (maxY,maxX) = readln().split(" ").map { it.toInt() }

    val inputArr = Array(maxY){IntArray(maxX)}
    val visitArr = Array(maxY){BooleanArray(maxX)}
    val queue = ArrayDeque<List<Int>>()

    repeat(maxY){
        inputArr[it] = readln().chunked(1).map { it.toInt() }.toIntArray()
    }

    queue.addLast(listOf(0,0,1))
    while (queue.isNotEmpty()){
        val (y,x,count) = queue.removeFirst()
        if(y<0 || x<0 || y>=maxY || x>=maxX) continue
        if(inputArr[y][x] == 0) continue
        if(visitArr[y][x]) continue
        inputArr[y][x] = count
        visitArr[y][x] = true

        queue.addLast(listOf(y+1,x,count+1))
        queue.addLast(listOf(y-1,x,count+1))
        queue.addLast(listOf(y,x+1,count+1))
        queue.addLast(listOf(y,x-1,count+1))
    }
    println(inputArr[maxY-1][maxX-1])
}

 

중심을 잡고 가장 가까운 주변부터 차례차례 탐색 및 큐에 삽입하는 로직을 구성한 후,

큐의 선입선출 특징을 살려 순서대로 해결하는 방법입니다.

 

이런 타입은 결국 많이 풀어야 감을 잡을 수 있을것 같습니다ㅎㅎ

 

 

 

 

궁금한 점 질문, (정중한)조언을 매우 매우 환영하니 부담 없이 댓글 부탁드려요!