[알고리즘] DFS와 BFS

이호영·2021년 7월 23일

CodingTest python

python

목록 보기

10/13

깊이 우선 탐색 (DFS)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

어떤 경우에 DFS를 사용하나?

모든 노드를 방문하고자 하는 경우
경로의 특징을 저장해야하는 경우

DFS의 특징

스택형식의 알고리즘을 사용한다.
재귀함수를 사용할 수 있다.

DFS 구현 (python)

// 문제가 dfs라 생각되면 해당 graph를 설계를 하고난후 밑에 코드만 접목시키면 된다.
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 방문노드
visited = [False] * len(graph)

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    
    for i in graph[v]:
        if not visited[i]:
            visited[i] = True
            dfs(graph, i, visited)

# 0번 노드가 없으니 1번 노드부터 탐색
 dfs(graph, 1, visited)

DFS 예제

넓이 우선 탐색 (BFS)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

어떤 경우에 BFS를 사용하나?

주로 두 노드 사이의 최단 경로를 구하는 경우
깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것

BFS의 특징

큐형식의 알고리즘을 사용한다.
재귀적으로 동작하지 않는다.

BFS 코드 구현

def bfs(graph, v, visited):
	
    queue = deque([start])
    
    visited[v] = True
    while queue:
    	v = queue.popleft()
        print(v, end=' ')
    
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 방문노드
visited = [False] * len(graph)

# 0번 노드가 없으니 1번 노드부터 탐색
 bfs(graph, 1, visited)

DFS와 BFS 예제를 풀어보자

level2. 타겟넘버

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

bfs 풀이

import collections

def solution(numbers, target):
    answer = 0
    stack = collections.deque([(0, 0)])
    while stack:
        current_sum, num_idx = stack.popleft()

        if num_idx == len(numbers):
            if current_sum == target:
                answer += 1
        else:
            number = numbers[num_idx]
            stack.append((current_sum+number, num_idx + 1))
            stack.append((current_sum-number, num_idx + 1))

    return answer

dfs 풀이

from collections import deque


def solution(numbers, target):
    
    answer = 0
    
    n = len(numbers)
    
    def dfs(index, value):
        
        nonlocal answer 
        
        if index == n:
            if value == target:
                answer += 1
            return
        else:
            dfs(index + 1, value + numbers[index])
            dfs(index + 1, value - numbers[index])
            
    dfs(0,0)

    return answer

풀이 후 느낀점

이 문제는 dfs와 bfs 둘다 사용 가능하다.
전체 탐색을 하는 경우라서 dfs를 사용하는 경우가 더 많은 것 같다~

level3. 네트워크

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

dfs 풀이

def solution(n, computers):
    answer = 0
    arr = []

    for index, data in enumerate(computers):
      a = []
      for i,d in enumerate(data):
        if i != index and d == 1:
          a.append(i)

      arr.append(a)
    
    def dfs(s):
      visited[s] = 1

      for i in arr[s]:
        if visited[i] == 0:
          dfs(i)

    visited = [0] * len(arr)

    for i in range(n):
      if visited[i] == 0:
        answer += 1
        dfs(i)
    
    return answer

풀이 후 느낀점

전형적인 dfs풀이, 전체를 순회해야하기 때문에!
dfs 알고리즘코드를 이용하였다.
문제의 입력값을 통해 graph를 구현하였고 dfs stack 사용구조를 그 대로 가져와서 순회가능한 경우의 수를 구하였다.

level3. 단어 변환

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

한 번에 한 개의 알파벳만 바꿀 수 있습니다.
words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면
"hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

초기 풀이

def solution(begin, target, words):
    answer = 0
    
    // 바꿀수있는 단어를 반환해주는 함수
    def search(a):
        arr = []

        for j in words:
            n = 0
            for i in a:
                if i in j:
                    n += 1

            if n == 2:
                arr.append(j)
        return arr
    
    aa = []

    if target in words:

        ar = [begin]

        while True:
            for i in ar:
                aa = search(i)

            if target in aa:
                answer += 1
                break

            answer += 1
            ar = aa
    
    return answer

bfs 풀이

from collections import deque

def solution(begin, target, words):
    answer = 0
    isVisited = [False]*len(words)
    queue = deque()
    if not target in words :
            return 0

    for i in range(len(words)) :
        
        if(searchSimilar(begin,words[i])) :
            queue.append([1,words[i]])
            isVisited[i] = True
            if words[i] == target :
                    answer = 1
                    return answer
            

   
    while queue :
       
        v = queue.popleft()
       
        for i in range(len(words)) :
            if(searchSimilar(v[1],words[i]) and isVisited[i] == False) :
            
                queue.append([v[0]+1,words[i]])
                isVisited[i] = True
                
                if words[i] == target :
                    answer = v[0] + 1
                    return answer
        
    return 0  


def searchSimilar(begin,word):
    difcount = 0
    for i in range(len(begin)) :
        if begin[i] != word[i] :
            difcount +=1
    if difcount == 1 :
        return True  
    return False

풀이 후 느낀점