본문 바로가기
코딩테스트

DFS와 BFS - 특정 연결을 찾을 때

by 임지혁코딩 2024. 1. 22.

코딩 테스트에서 가장 자주 활용되는 개념으로, 이 개념을 이렇게 빨리 접할 줄은 몰랐다.

 

그러나 개념 상에서 TREE를 사용하는 것이고 파이썬에선 주로 

재귀의 형태로 이를 호출하기 때문에, 이 문제가 재귀 문제에 포함 되어 있어 이렇게 빨리 DFS와 BFS를 접하게 되었다. 

 

DFS란, 깊이 우선 탐색이라고 한다. 

 

모든 노드를 탐색하는 것을 기반으로 한다 .

 

 그 순서는

1. 내 자식을 왼쪽부터 검사한다.

2. 내 자식의 자식이 있다면 , 그 자식의 자식( 손자)를 검사한다 .

3. 내 자식의 자식을 모두 검사했거나 없다면, 다음 오른쪽 자식을 검사한다. 

 

BFS란, BEST가 아니었다..! 

너비 우선 탐색으로

 

그 순서는

1. 내 자식을 왼쪽 부터 검사한다 .

2. 그 다음 (같은 LEVEL의 ) 자식을 오른쪽으로 넘어가며 검사한다. 

3. 반복

 

https://hudi.blog/dfs-bfs/ 

 

[ALG] DFS/BFS (깊이/너비 우선탐색)

본 포스트는 저자가 학습하며 작성한 글 이기 때문에 틀린 내용이 있을 수 있습니다. 지적은 언제나 환영입니다. 1. 서론 DFS/BFS 는 그래프 자료구조에 기반한 대표적인 '탐색' 알고리즘이다. 그래

hudi.blog

 

이 블로그의 에니메이션을 참고했다. 감사합니다. 

 

 

해당 개념을 사용하는 경우는 , 

1. 최소거리, 최단거리 탐색

2. 연결되어있는 갯수를 구하는 네트워크형 문제

3. 모든 조합을 만드는 문제 . 

 

구현 방식은 어떡할까? 

주로 재귀를 사용한다 .

 

1. 재귀의 끝의 탈줄 조건에 도달한다. ** 끝 조건 부터 구하는 것이 재귀의 기본이다. 

2. 그 이후 변수가 변경되어 재귀 된다. 

 

주로 DFS나 BFS중 한개를 기본적으로 사용한다. 

나는 알고리즘 상황에서 (항상은 아니지만) DFS가 검증하기가 쉽다는 내용을 배웠다. 

 

너무 많은 LEVEL이 나오는 경우에는 BFS를 사용하자 . 

 

 

 

실제 구현 

실제 구현시는, GRAPH화를 하는 방법을 꺠달아야 한다. 

내가 방문한 NODE에 대해서 COUNT를 해야하기 때문이다. 

 

가장 기본적인, 음료수 얼려 먹기 문제를 확인해보겠다. 

 

문제

N, M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

 

풀이

1. 상하좌우를 살펴보고 0이 있으며, 아직 방문하지 않았다면 해당 지점 방문 . 

2. 방문한 곳에서 살펴보고 , 없거나 다 방문했다면 방문하지 않음 

3. 이 시작점을, 모든 노드로 기준점을 바꿔준다. 

4. 방문하지 않은 지점을 카운트하면 된다. 

 

이를 좀더 쉽게 말하자면,

특정 지점에서 시작하여 모든 갈 수 있는 곳을 가고 .

그 곳들을 전부다 갔을때는 방문한 곳들은 더이상 방문할 수 없다고 표시한다 . (이미 방문했다)

모든 곳을 다 방문하고 나면, count를 1개 추가한다. 

 

 

import sys

strn,strm = sys.stdin.readline().split()
N= int(strn)
M= int(strm)

graph = []
for i in range(N) :
    graph.append(list(map(int,sys.stdin.readline().rstrip())))
 

입력을 받는다. 이는 쉽다 .

 

def dfs(x,y) :
    if x<= -1 or x>= n or y <= -1 or y >= m :
        return False
   
    if graph[x][y] == 0 :
        graph[x][y] == 1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x,y-1)
        return True
    return False

이 함수를 설명해보겠다. 

 

종단의 조건 : 

 특정 목표에 달성하면 종단하는 형태가 아니다. 

 (모든 곳을 돌아야 하기 때문에!!! )

 그래서, 범위를 넘었을때를 종단의 조건으로 두었다. 

 

시작점에서 출발하여 방문하는 곳들은, 모두 1 로 처리했다. 

이제 연결된 점에서 어떤 점에서 시작해도, 방문하는 곳은 1이 되어 그곳을 더이상 돌지 않게 된다.

 

모여있는 곳들을 모두 돌았을때만 true가 나올 것이다 .

 

result = 0
for i in range(N):
    for j in range(M) :
        if dfs(i,j) == True :
            #다 돌았다면. 내가 갈수있는 곳은 다 간 상태라면
            result = result + 1

print(result)

 

graph의 모든 점에서 시작한다. 해당 점과 연결된 곳이 이미 내가 도달했던 곳이라면, 자연스럽게 false가 나와 

돌지 않는다. 

 

#dfs의 종단 조건 ! 

1. 모든 경우를 다 돌아야 한다면 

 - 범위를 넘쳤을때 종단한다. (자동으로 종단될 것이라는 생각을 버리자) 

2. 특정 경우를 찾는다면

 - 범위를 넘쳤을때 종단한다. 

 - 특정 경우를 찾았을때도 종단한다.  

 

단순 재귀와의 종단 차이 :

단순 재귀는, divide and conquer처럼 이미 정해진 경우 , 혹은 범위를 탈출하기 전에 미리 값이 나오는 경우가 있다. 

(크기가 1일때 값이 3 과 같이, 크기가 범위를 넘기전 결과가 나온다. ) 

 

 

BFS

일단 QUEUE를 사용한다 . 

그래프에서 가까운 노드들을 먼저 탐색한다 (끝까지부터 가는 것이 아니다) . -> QUEUE를 사용한다. 

 

QUEUE를 쓰는 이유? DFS는 1 -> 2 ->5 ->이런식으로 가기 때문에 재귀 만으로 표현이 가능하다.

허나 BFS는 1 ->2 , 1-> 3 , 1->4 이후 2-> 5 이런식으로 방문한다. 그러므로 QUEUE가 필요하다!

(FIRST IN FIRST OUT) (파이썬에는 POP(0)) 혹은 DEQUE

 

BFS는 다음과 같이 푼다 .

 

1. queue에 시작점을 정리한다. (시작점을 방문함을 표현한다) 

 

   q = deque([node])

이렇게! 

2. queue에서 pop하고, 그 pop한 곳과 연결되어 있는 곳을 간다. 

3. 이때 pop한 곳은 방문함을 처리한다 .

4. 시작점에서 이어진 곳을 다 갔다면, 그 다음 queue에서 pop해서 그곳에서 간다 .

5. 이 과정을 반복한다. 

 

6. 재귀가 아니다 ! 

'코딩테스트' 카테고리의 다른 글

DFS /BFS - 순환 그래프 수 찾기  (1) 2024.01.25
DFS와 BFS - 특정 점에서 모든 경로를 찾을 때  (0) 2024.01.23
재귀  (0) 2024.01.21
Stack, Queue, Deque  (0) 2024.01.11
SET, MAP  (0) 2024.01.07