[PROGRAMMERS] 프로그래머스 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) 파이썬 문제풀이

프로그래머스 코딩테스트 연습 > 고득점 kit > 깊이/너비 우선 탐색(DFS/BFS) 파트 문제풀이 파이썬 https://programmers.co.kr/learn/courses/30/parts/12421

프로그래머스

 

 

그래프 (Graph)

정점과 간선으로 이루어진 자료구조

그래프 탐색 : 특정 노드를 시작으로 모든 노드를 한번씩 방문하는 것

 

* 트리는 일종의 그래프, 그래프는 트리와 달리 정점마다 간선이 있을수도 있고 없을 수도 있으며 루트 노드와 부모, 자식 노드의 개념이 없음

 

graph = {
    # 노드 : [간선으로 이어진 노드들]
    'A': ['B'],
    'B': ['A', 'C', 'H'],
    'C': ['B', 'D'],
    'D': ['C', 'E', 'G'],
    'E': ['D', 'F'],
    'F': ['E'],
    'G': ['D'],
    'H': ['B', 'I', 'J', 'M'],
    'I': ['H'],
    'J': ['H', 'K'],
    'K': ['J', 'L'],
    'L': ['K'],
    'M': ['H']
}

 

 

깊이 우선 탐색 (DFS, Depth-First Search)

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

예를 들어 미로에서 한 루트로 계속 가다가 막다른 길이면 바로 직전 갈림길로 돌아가 길을 찾는 방법이라할 수 있음

모든 노드를 탐색하고자할 때 사용

BFS보다 간단하나 검색 속도 자체는 BFS에 비해 느림

자기 자신을 호출하는 순환형태

* 어떤 노드를 방문했는지 노드 방문 검사를 꼭 해야함 > 스택(stack, 후입선출)을 이용하여 방문한 노드 저장

 

파이썬 DFS (비재귀ver)

def dfs(graph, root):
    visited = []
    stack = [root]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack.extend(graph[n])
            # stack += graph[n] - set(visited)
    return visited

파이썬 DFS (재귀ver)

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

 

 

너비 우선 탐색 (BFS)

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

시작 노드로부터 가까운 노드부터 방문하고 멀리 있는 노드는 나중에 방문

두 노드 사이 최단 경로를 찾거나 임의의 경로를 찾고싶을 때 사용

재귀적으로 동작하지 않음

* 어떤 노드를 방문했는지 노드 방문 검사를 꼭 해야함 -> 자료구조 큐(queue, 선입선출) 사용하여 방문한 노드를 차례로 꺼냄

 

파이썬 BFS

def bfs(graph, start_node):
    visit = list()
    queue = list()

    queue.append(start_node)

    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])
 
    return visit

 

 

++ 거의 다 답안 코드 참고해서 풀었는데 탐색 관련해서 더 공부해서 다시 풀어봐야겠다.. 힝

 

 

타겟넘버 (Level 2)

깊이우선탐색을 해야한다.

주어진 리스트이 길이만큼의 높이에 1과 -1로 채워진 트리에서 루트 0부터 마지막까지 따라가 가장 마지막 노드에 있는 값들이 나올 수 있는 수이다.

 

 

 다른 사람 코드1 

import collections

def solution(numbers, target):
    answer = 0
    stack = collections.deque([(0, 0)]) # 방문한 노드 - 양방향 큐
    
    while stack:
        sum, idx = stack.popleft()

        if idx == len(numbers): # 1의 수(numbers의 길이)와 트리 높이가 같아질때까지 그래프 생성
            if sum == target:
                answer += 1
        else:
            # -1, 1 더한 그래프 생성
            number = numbers[idx]
            stack.append((sum + number, idx + 1))
            stack.append((sum - number, idx + 1))

    return answer

 

 다른 사람 코드2 

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

 다른 사람 코드3 

def dfs(nums, i, n, t):
    answer = 0
    
    # 그래프 구성 후 값 비교
    if i == len(nums):
        if n == t:
            return 1
        else:
            return 0
    
    # 재귀 호출하여 그래프 구성
    answer += dfs(nums, i+1, n+nums[i], t)
    answer += dfs(nums, i+1, n-nums[i], t)
    return answer

def solution(numbers, target):
    answer = dfs(numbers, 0, 0, target)
    return answer

 

 

네트워크 (Level 3)

예시1 설명)

n	computers	output
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2

 

 

예시2 설명)

n	computers	output
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

 

 

 다른 사람 코드1 

def solution(n, computers):
    answer = 0

    visited = [False for i in range(n)]

    for com in range(n):
        if visited[com] == False:
            DFS(n, computers, com, visited)
            answer += 1 # 탐색이 끝나면 네트워크 완성
    return answer

def DFS(n, computers, com, visited):
    # 전체 노드 수, 연결 정보, 현재 노드, 방문 노드 정보

    visited[com] = True # 현재 노드 방문 체크

    for connect in range(n):
        if connect != com and computers[com][connect] == 1: # 연결된 컴퓨터
            if visited[connect] == False:
                DFS(n, computers, connect, visited)

 다른 사람 코드2 

def solution(n, computers):
    temp = []

    for i in range(n):
        temp.append(i) # 전체 노드 정보 저장

    # 하나의 네트워크로 연결될 때 동일한 값으로 바꿔줌
    for i in range(n):
        for j in range(n):
            if computers[i][j]: # 1이면, 연결되어 있으면
                for k in range(n): 
                    # i->j, j->k 이면 i->k 임을 이용
                    if temp[k] == temp[i]:
                        temp[k] = temp[j]

i->j 연결되어 있고 j->k가 연결되어있으면 i->k가 연결 가능한 점을 이용하여 3중 for문을 통해 해결하였다.

효율성 부분에서 문제가 있을 수 있긴 직관적으로 이해하기 쉬운 코드인 것 같다.

 

 

단어 변환 (Level 3)

후에 추가할 예정..

 

 내 코드 

 

 다른 사람 코드