알고리즘은 탐색이야

박재성·2022년 5월 23일

그리디만 풀었다.

유튜브 '동빈나'님의 채널에서 얻은 정보로 알고리즘의 시작은 '그리디'라는 생각으로 시간이 날 때마다 그리디를 풀어왔다.

아직 그리디를 잘 푸는 것은 아니지만 백준의 실버문제는 풀 수 있는 정도가 되었다. 목표로 잡았던 ac 점수 골드도 달성을 했기 때문에 마냥 내 실력이 올랐을 거라는 기대감을 가졌지만 탐색을 풀어보니 결과는 너무 처참했다.

그리디를 많이 풀어도 망할 구현력은 왜 나아지지 않을까 하는 생각이 많이 들었다. 그 동안 풀었던 문제를 다시 풀어보며 진짜 내가 푼 것이 맞는지 확인해야 되겠다는 생각을 하게 됐다.

탐색은 왜 못 풀까

내가 지금까지 너무 쉬운 문제만 풀었던 것 같다. 그리디 문제도 어렵다고 느꼈지만 대부분 짧게 끝내는 문제들을 많이 풀었었다. 많이 반성한다. 실력 향상보다 티어에 더 신경을 썼나 보다.

너비우선 깊이우선

두 알고리즘은 굉장히 간단하다. 그래프에서 각 노드를 수직으로 탐색하는지 넓게 하는지의 차이가 있다.

알고리즘의 개념이 어려운 것은 절대 아니다. 엄밀히 말하면 이미 끝났다. 하지만 나는 왜 탐색 문제에 어려움을 느꼈을까

그것은 역시 재귀함수를 구현하는 일이 까다롭다고 느꼈다. 재귀함수 구현이 어렵다는 것은 사실 구현력이 아직도 많이 부족하다고 생각한다. 그리디를 가장 많이 푼 것이지 절대적으로 많이 풀었던 것은 아니었다.

너비우선

우리는 너비우선 탐색을 'bfs'라고 정의하고 시작노드에서 가까운 순서대로 탐색을 진행한다. 그래서 두 노드 간 최단거리를 찾을 때 알맞은 알고리즘이다.

깊이 우선

깊이 우선은 너비 우선과 차이가 있다면 다른 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다는 것이다. 즉 길찾기에서 유용하게 쓸 수 있는 알고리즘이다. 그럼 공부한 내용을 토대로 직접 구현을 해봐야한다. 안되면 외워서라도 사용하자

구현

깊이우선 탐색 (DFS)

탐색을 구현하는 여러가지 방법이 있지만, 재귀함수를 이용해서 구현을 해보자

def dfs(graph, startNode, visited):
	visited.append(startNode)
    for node in graph[start]:
    	if node not in visited:
        	dfs(graph, node, visited)
    return visited

노드와 간선을 나타내는 graph obj를 구현하고, 방문한 것을 visited에 저장해서 탐색 완료를 나타내고, 해당 노드가 탐색이 완료되지 않은 노드일 경우 재귀함수를 호출해 더 깊은 depth로 내려가는 것이다.

문제 적용

백준 260번 바이러스

해당 문제는 깊이 우선 탐색을 가장 기본적으로 풀 수 있는 문제이다. 기본적으로 dfs 구현이 가능하다면 쉽게 풀지만, 나는 탐색을 너무 몰랐다.

여기서 한 가지 알아야 할 것은 노드와 노드 사이 연결 관계를 입력으로 주어질 때 어떻게 처리를 해야하는지 알아야 한다.

graph = {}

for i in range(N):
    graph[i+1] = set()

for _ in range(M):
    start, end = map(int, input().split())
    graph[start].add(end)
    graph[end].add(start)

해당 문제에서는 번호로 입력이 주어지기 때문에 graph의 각 항목들을 set()으로 초기화를 진행했다. 1번 노드와 연결된 노드가 set의 요소로 들어가게 되면서 깔끔하게 노드 간 관계를 알 수 있다.

적절하게 필요한 데이터를 전부 얻었기 때문에 dfs 로직을 적용하면 된다.

def dfs(dict, startNode, visited):
	for node in dict[startNode]:
    	if node not in visited:
        	visited.append(node)
            dfs(dict, node, visited)

전체 코드

N = int(input())
M = int(input())

graph = {}
for i in range(N):
    graph[i+1] = set()
print(graph)
visited = []
for _ in range(M):
    start, end = map(int, input().split())
    graph[start].add(end)
    graph[end].add(start)

def dfs(dic, startNode):
    for i in dic[startNode]:
        if i not in visited:
            visited.append(i)
            dfs(dic, i)

dfs(graph, 1)

print(len(visited)-1)

너비우선 탐색 (BFS)

dfs를 구현하면서 이미 필요한 데이터는 준비 했다. bfs 함수를 작성해보자

def bfs(dic, startNode, visited):
	queue = deque()
    queue.append(startNode)
    
    while queue:
    	pop = queue.popleft()
        
        for node in graph[pop]
        	if node not in visited:
            	visited.append(node)
                queue.append(node)