[알고리즘, Python] 프로그래머스 고득점 Kit - DFS/BFS

그래프 기본 설명

• 노드(Node)와 간선(Edge)로 표현되며, 이 노드를 정점(Vertex)라고 말함
• 그래프 탐색이란 하나의 노드를 시작으로, 다수의 노드를 방문하는 것
• 두 노드가 간선으로 연결되어 있다면, 두 노드는 인접하다(Adjacent)고 표현
• 그래프와 트리의 차이: 그래프 중에서 방향성이 있는 비순환 그래프 = 트리

그래프 표현 방법

1. 인접행렬: 2차원 배열로 그래프의 연결 관계를 표현
2. 인접리스트: 리스트로 그래프의 연결 관계를 표현

# 인접행렬
INF = 99999999

matrix = [
	[0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(matrix)
===> [[0, 7, 5], [7, 0, 99999999], [5, 99999999, 0]

# 인접리스트
list = [[] for _ in range(3)] # [] 안에 리스트 세개

list[0].append((1, 7)) # 노드 0에 연결된 노드 정보 저장 (노드, 거리): 튜플 추가라서 괄호 두개
list[0].append((2, 5)) 
list[1].append((0, 7)) # 노드 1에 연결된 노드 정보 저장 (노드, 거리)

print(list)
===>
[[(1,7), (2,5)], [(0, 7)]

 

DFS (Depth-First Search)

최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

스택 자료 구조를 이용

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리
   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄 (= 옆으로 이동)
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

방문처리: 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미 → 각 노드를 한 번씩만 처리하도록 

 

⇒ DFS는 재귀 또는 스택으로 구현 가능

DFS 사진 (출처: https://developer-mac.tistory.com/64)

DFS 예제 - 재귀

# g = graph, v = visit, visited = visited

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

g = [
	[], # 0
    [2, 3, 8], # 1번 노드와 연결된 노드들
    [1, 7], # 2번 노드와 연결된 노드들
    [1, 4, 5], # 3번 노드와 연결된 노드들
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
dfs(g, 1, visited)

===>
1 2 7 6 8 3 4 5

DFS 예제 - 스택

def dfs(v):
	dfs_stack = [v]
    	while dfs_stack:
    		nv = dfs_stack.pop()
        
        	if visited[nv] == 1:
        		continue
        	print(nv, end = ' ')
        
        	vistied[nv] = 1
        	dfs_stack.extend(reversed(graph[nv]))

reversed() 는 작은 숫자 노드를 먼저 방문하기 위해서이므로, 낮은 노드를 먼저 방문할 필요는 X

> append()와 extend()의 차이

• append(x) : x 그 자체를 리스트의 맨 마지막 요소로 추가
• extend(x): x가 iterable이어야 한다는 조건이 있으며, iterable의 요소를 하나씩 꺼내어 list의 맨 끝부분부터 채워넣는다고 생각

 

BFS (Breadth-First Search)

최대한 넓게 이동한 다음, 더이상 갈 수 없을 때 아래로 이동

큐 자료 구조를 이용: 인접한 노드를 반복적으로 큐에 넣으면, 자연스럽게 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색을 하게 됨

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

BFS 사진 (출처: https://developer-mac.tistory.com/64)

 

BFS 예제

from collections import deque

def BFS(g, start, visited):
	queue = deque([start])
	visited[start] = True
    
    while queue:
    	v = queue.popleft()
        print(v, end= ' ')
        for i in g[v]:
    		if not visited[i]:
        		queue.append(i)
                visited[i] = True

g = [
	[], # 0
    [2, 3, 8], # 1번 노드와 연결된 노드들
    [1, 7], # 2번 노드와 연결된 노드들
    [1, 4, 5], # 3번 노드와 연결된 노드들
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
bfs(g, 1, visited)

===>
1 2 3 8 7 4 5 6

 

---

프로그래머스 문제

💡 타겟 넘버 (Lv.2)

코테에서는 카테고리가 정해져 있지 않기 때문에 어떻게 하면 이 문제의 알고리즘을 알 수 있을까에 대한 고민

→ 예제를 보고 +와 - 두가지로 이진 분류를 할 수 있다는 것을 깨달음

→ 그래프를 사용해야할텐데 노드 끝까지 가서 target과 비교하는 과정이 필요하다고 생각해서 DFS를 사용해야된다!고 생각

→  +와 -를 분기처리를 해야된다고 잘못 생각 + 리스트 안 원소들을 for문으로 처리해야된다고 잘못 생각

 

나의 풀이: DFS - 재귀함수

counter = 0

def solution(numbers, target):
    total = 0
    dfs(0, numbers, total, target)
    
    return counter
    
def dfs(idx, numbers, total, target):
    global counter
    
    if(idx == len(numbers)):
        if total == target:
            counter += 1   
    else:
        dfs(idx+1, numbers, total+numbers[idx], target)
        dfs(idx+1, numbers, total-numbers[idx], target)

• 전역변수를 변경하기 위해선 global 표시를 해야됨 (읽기만 하는 경우에는 global 표시 X, 만약에 작성 안 할경우 UnboundedLocalError 발생)

 

BFS

def solution(numbers, target):
    answer_list = [0]
    
    for num in numbers:
        temp_list = []
        for _ in range(len(answer_list)):
            temp = answer_list.pop()
            temp_list.append(temp + num)
            temp_list.append(temp - num)
        
        answer_list = temp_list.copy()
      
    return answer_list.count(target)

• temp와 num의 위치에 따라서 달라짐 (num-temp로 했는데 계속 값이 안나옴): num을 먼저 하면 안되는 이유가 원래 값에 num을 더하고 빼야됨
• 기존 리스트에 계속 추가하는 방법은 copy()를 쓰는 것!!

 

💡 네트워크 (Lv.3)

 

나의 풀이: BFS

from collections import deque

def solution(n, computers):
    answer = 0
    queue = deque([0])
    visited = [0] * n
    
    for i in range(n):
        if visited[i] == 0:
            visited[i] = 1
            answer += 1
            queue.append(i)
        
        while queue:
            v = queue.popleft()

            for idx, net in enumerate(computers[v]):
                if (visited[idx] == 0) & (net == 1):
                    visited[idx] = 1
                    queue.append(idx)

    return answer

→ queue에 이어서 넣고 빼는걸 반복함으로써 구할 수 있다고 생각해서 BFS로 풂

→ while queue 부분까진 생각했으나, 안 이어지는 부분들을 count해야된다는 것을 고려해서 밖에 for 문을 한 번 더 감쌌음

→ enumerate를 써서 간편하게 index와 원소에 접근