🏀 개요

알고리즘 중 탐색 부분에 대해서 공부하고자 한다.

아직 많은 코딩테스트를 경험한 것은 아니지만, 탐색 문제는 매 번 나온다고 느꼈다.

물론 탐색의 종류는 많지만, 이번에는 DFS/BFS을 알아보고자 한다.

참고 :
동빈나 유튜브 채널을 기반으로 정리한 것으로, 유튜브 링크를 첨부 하겠습니다.
동빈나 유튜브 링크

💡 접근 방식

일단 DFS/BFS를 알기 위해서는 스택, 큐, 재귀 함수를 알아야한다. 재귀함수는 DFS에서 깊이를 보장하기 위해서 사용되고, 스택 또한 DFS, 큐는 BFS에서 사용된다.

기본적으로 사용 되는 구성은 노드간의 관계를 나타내는 graph, 방문 여부를 체크해주는 visited list, 각 기준에 맞게 사용되는 스택, 큐 라고 생각하면 된다. 각 요소에 대해서 알아보자.

graph
이중 리스트 형식으로 인접한 노드의 정보를 알려주는 자료 구조라고 생각하면 된다. 현재, 간선의 가중치는 동일하니 고려하지 않는 그래프라고 생각하면 된다.
[
[], #그래프 0 번째는 보통 노드의 시작이 1이므로 빈 값처리.
[2,3,8], # 1번째의 노드는 2,3,8 노드와 연결 되어 있다고 이해할 수 있다.
[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7] # 위와 동일하게 이해 가능
]

그림을 보여주면 이해에 도움되지만.. 패스..ㅎ_ㅎ

visited list
visited = [False] * len(graph) # 각 노드 별 방 여부를 체크하기 위함.
스택과 큐에서 가져온 노드에 대해서 방문 여부를 판단해야, 그래프를 탐색을 이어갈 수 있다.
보통

if visited[i] == False:
	dfs(g,i,visited) or bfs(g,i,visited) 

이런 식으로 사용한다고 이해하면 좋다.

스택과 큐에 대해서는 각 기법을 보면서 이해하면 좋을듯 해서 여기선 설명하지 않을 예정!

💎 DFS

깊이 우선 순위 탐색. 즉, 인접 노드를 탐색하는 기준을 깊이로 잡고 탐색한다고 생각하면 된다. 이 깊이라는 걸 보장하기 위해서 stack을 사용한다.

가장 핵심적인 요소인, 깊이 우선으로 노드를 접근하는 방식을 설명해보려고 한다.

앞에서 말한 것 처럼 인접노드 정보는 graph에서 알려주고, 각 노드에 대해서 순회해야 하므로 그래프를 반복문으로 접근 해야한다.

for i in graph[v]:
	if not visited[i]:
    		dfs(graph,i,visited)

v 는 시작점으로 파라미터로 넘겨줄 예정임.

즉, 시작점에 대한 인접 노드 list를 받아와 순회함으로서 깊이 우선적으로 접근이 가능하다.
만약 이 부분이 이해가 안된다면, 재귀함수의 작동원리를 고려해서 다시 보면 이해에 도움이 될 것이다.

그럼 핵심이 아닌 전체적인 코드로 본다면

def dfs(graph,v,visited):
	visited[v] = True # 방문 처리
    	print(v, end = " ") # 순서를 보여주기 위한 출력
    	for i in graph[v]: # 인접노드리스트 받아오기
    		if not visited[i]: # 방문 안한 경우에만 방문하도록
        		dfs(graph,i,visited) # 깊이를 우선하기 위해서 재귀 함수 사용!

이런식으로 실행 dfs(graph,1,visited)를 실행한다면, 1 2 7 6 8 3 4 5 라는 결과 값 생성.

💎 BFS

너비 우선 순위 탐색, 위와 동일하게 그래프를 탐색하지만, 같은 depth를 가진 노드를 우선적으로 탐색한다고 생각하면 된다. 이를 보장하기 위해서 queue를 통해 같은 depth 노드를 관리한다.
주요 특징은 간선의 가중치가 같을 때 노드 간의 최단 거리를 찾기에 적합한 방법이라는 것이다. 그 이유는 모든 노드에 대해서 거리를 계산하기 때문에 최단 거리를 알 수 있다.

코드를 통해 BFS를 보여줄 예정

def bfs(graph, start, visited):
	queue = deque[(start)] # 같은 depth를 보장하기 위해서
    visited[start] = True
    while queue: # queue를 통해 모든 노드를 순회하기 위함
    	v = queue.popleft()
        print(v, end = " ")
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True # 방문 처리
                

결국 목적에 맞게 자료구조나 재귀함수를 사용해서, 순서를 보장하고 전체적인 처리는 방문처리라는 것이 동일.

🔧 예제 문제

이 방법을 이해하고, 이 순회가 어떻게 사용될 것인지, 고민했다.

일단 기본적으로 탐색이라는 것을 기반으로
1. 모든 노드를 조회하는 경우 사용
2. 그래프 형식 즉, 이차원 리스트에 대해서 사용
순회 대상인 그래프가 위에 가정 처럼, 인접한 노드 정보가 아니더라도, x,y 좌표를 통해 노드가 인접하다는 걸 알 수 있고, 그래프 내용을 통해 방문 여부, 또는 방문 가능한 여부를 알게 된다면, 많은 곳에서 사용할 수 있다.

예제 문제에 대한 설명은 위에 첨부한 유튜브를 통해 살펴 볼 수 있다. 저는 이 문제를 풀면서 느낀점에 대해서 작성함.

추가로 제가 짠 코드를 아래에 첨부할 예정임.

음료수 얼려 먹기

def dfs(graph,x,y):
    n = len(graph)
    m = len(graph[0])
    
    if x < 0 or x >= n:
        return False
    if y < 0 or y >= m:
        return False
    
    if graph[x][y] == 0: # 각 값은 방문 가능 상태 
        # x,y를 통해 인접노드, 상하,좌우 모두 방문하여 상태값 변경
        dfs(graph,x+1,y)
        dfs(graph,x-1,y)
        dfs(graph,x,y+1)
        dfs(graph,x,y-1)
        return True # 접근 가능한 모든 노드를 방문하고 종료
    return False # 일단 방문이 안한다면 의미가 없다.

if __name__ == '__main__':
    n, m = map(int,input().split())
    graph = []
    for i in range(n):
        graph.append(list(map(int,input())))
    result = 0
    # 그래프 순회
    for i in range(n):
        for j in range(m):
            if dfs(graph,i,j) == True: # True 면 한 블럭에 대해서 다 처리 했다. 즉 , result를 1만큼 증가해라
                result += 1
    print(result)