[PROGRAMMERS] 그래프탐색 뽀개기 | 파이썬 | 프로그래머스 DFS/BFS 문제풀이

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

프로그래머스

 

Lv2. 타겟 넘버

n개의 음이 아닌 정수들이 주어질 때 이 정수들의 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 한다. 타겟 넘버를 만들 수 있는 방법의 수를 구하여라

 

1회차 풀때도 어려웠던 문제.. 다음 숫자  +와 -를 붙인 2가지 경우로 계속 뻗어나가는 트리 모양을 생각하면서 풀면 된다.

이번에도 안풀려서 이전 코드를 참고해 풀었다 ㅠ

def dfs(k, target, numbers):
    answer = 0
    try:
        if not numbers:
            if k == target:
                return 1
            else:
                return 0

        answer += dfs(k + numbers[0], target, numbers[1:])
        answer += dfs(k - numbers[0], target, numbers[1:])
        return answer
    
    except:
        print(answer, target, numbers)

def solution(numbers, target):
    return (dfs(numbers[0], target, numbers[1:])) + (dfs(numbers[0]*(-1), target, numbers[1:]))

 

 

Lv3. 네트워크

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미한다. 컴퓨터 A가 B와 직접적으로 연결되어 있고 B와 C가 직접적으로 연결되어 있을 때 A와 C도 간접적으로 연결되어 있어 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있다. 컴퓨터 개수 n, 연결에 대한 정보가 2차원 배열 computers로 주어질 때 네트워크의 개수를 구하여라

 

이전 백준에서 푼 문제처럼 큰 비연결 그래프 안의 연결 그래프 개수를 구하는 문제이다.

첫번째 시도) 정확도 30.8

def solution(n, computers):
    answer = 0
    try: 
        graph = [list() for i in range(n+1)]
        nodes = [i for i in range(n)]

        for i in range(n-1):
            for j in range(i+1, n):
                if (computers[i][j] == 1):
                # 노드마다 연결된 노드들 저장
                    graph[i].append(j)
                    graph[j].append(i)

        total_visited = []

        while True:
            if len(total_visited) == n: # 전체 방문 여부 확인
                break
            total_visited.extend(dfs(graph)) # 방문한 노드 추가
            total_visited.sort() # 정렬
            graph = graph[total_visited[-1]:] # 방문하지 않은 노드
            answer += 1

        return answer
    except:
        print(i, j, computers[i][j])

노드(컴퓨터)간 연결 정보가 백준과 다르게 이차원 배열 형태로 주어진다. 백준의 경우 양 끝의 노드 두 개를 한줄에 입력하여 간선 정보를 제공하였는데, 프로그래머스 문제의 경우 이차원 배열에서 각 행, 열이 노드 번호이고 노드 사이 간선이 있을 때 해당 노드 번호 행열이 교차하는 지점에 1을 표시하여 정보를 제공한다.

먼저 이차원 배열 computers를 순회하며 간선 정보를 이차원 배열에 저장했다. 이번에는 사전이 아니라 리스트 배열(graph)로 각 노드 번호가 인덱스이고 해당 노드에 연결된 노드들 정보를 동적으로 리스트에 추가했다. 그리고 노드 방문 여부를 알기 위해 total_visited에 탐색이 한번 끝날 때마다 방문한 노드들을 추가하였고 남은 노드들에 대해 다시 DFS를 하였다. 노드 정보를 계속 정렬하기 때문에 방문하지 않은 노드들을 슬라이스로 잘랐다.

 

연결 그래프 탐색을 위한 DFS 코드

def dfs(graph):
    stack = [0]
    visited = []

    while stack:
        node = stack.pop()
        if node not in visited:
            stack.extend(graph[node])
            visited.append(node)
    
    return visited

연결 그래프를 파악하기 위해 모든 노드를 탐색해야 함으로 DFS를 선택했다. 안되는 이유를 정확히 찾지는 못하였지만 실패

 

두 번째 시도) 통과 

def solution(n, computers):
    answer = 0
     
    visited = [False for i in range(n)]
    for computer in computers:
        if visited[computer] == False:
            dfs(computers, visited, computer)        
     
    for i in range(n-1):
        for j in range(i+1, n):
            if (computers[i][j] == 1):
                graph[i].append(j)
                graph[j].append(i)

    return answer

def dfs(computers, visited, start):
    visited[start] = True
    for node in computers:
        if node not in visited:
            dfs(computers, visited, node)
    return visited

이전 백준 풀때 쓴 것처럼 굳이 집합 연산이나 슬라이싱으로 방문한 노드와 방문하지 않은 노드를 파악하지 않고 visited 배열을 인자로 전달받고 반환하며 그래프 안 모든 노드를 방문하도록 하였다. 구글링 참고함!

 

다른 사람 코드) 비재귀 버전

def solution(n, computers):
    answer = 0
    bfs = []
    visited = [0]*n

    while 0 in visited:
        x = visited.index(0)
        bfs.append(x)
        visited[x] = 1
        
        while bfs:
            node = bfs.pop(0)
            visited[node] = 1
            for i in range(n):
                if visited[i] == 0 and computers[node][i] == 1:
                    bfs.append(i)
                    visited[i] = 1
        answer += 1
    return answer

다른 사람 코드2) 재귀 버전

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)

 

---

아직 안 푼 문제들

Lv3. 단어 변환

Lv3. 여행경로