[TIL] DFS & BFS 특집! | 프로그래머스 - 네트워크 / 백준 - 바이러스 / 프로그래머스 - 타겟 넘버 / 백준 - 숨바꼭질

[Today I Learned]

대충 DFS와 BFS를 뽀개보겠다는 의지를 담은 제목.

# 프로그래머스 - 네트워크

문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항
컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
computer[i][i]는 항상 1입니다.

 

@solution.py

visited 리스트를 만들어두고 연결되지 않은 네트워크로 건너갈 때는 visited의 for문이 동작한다는 점을 이용해 풀이했다. BFS 재귀는 진짜 생각 못하겠어서 일단 DFS로 먼저 풀어봤다.

# BFS

from collections import deque

def solution(n, computers):
    
    visited = [False] * n
    network = 0
    
    for no in range(n): # n - 노드 넘버
        if not visited[no]: # 아직 방문 X
            visited[no] = True
            queue = deque([no])
            
            while queue:
                v = queue.popleft()
                
                for i,j in enumerate(computers[v]):
                    if j == 1:
                        if not visited[i]:
                            queue.append(i)
                            visited[i] = True

            network += 1
            
        else:
            continue
    
    return network

처음에는 queue 초기화하는 코드가 for문 밖에 있었는데, 그럼 0번 노드가 포함되지 않은 노드를 돌 때부터는 queue가 텅 비어있어서 while문을 계속 건너뛰게 된다. 따라서 while문 시작 전에 queue를 초기화할 수 있도록 코드를 변경했다.

그 다음은 다시 DFS 도전.

# dfs
def solution(n, computers):
    
    visited = [False] * n
    network = 0
    
    def dfs(computers,no,visited):

        visited[no] = True
        
        for i, j in enumerate(computers[no]):
            if j == 1:
                if not visited[i]:
                    bfs(computers,i,visited)

    for no in range(n): # n - 노드 넘버
        if not visited[no]: # 아직 방문 X

            dfs(computers,no,visited)

            network += 1

        else:
            continue
    
    return network

기본 큰 틀을 잘 잡아 이해해서 그런가? 훨씬 풀기 수월했다.  

 

# 백준 - 바이러스 

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

네트워크와 유사한 문제.

 

@solution.py

가장 처음에는 1번 노드를 기준으로 연결된 곳만 쭉 돌고, visited에서 True 값을 세면 되지 않을까? 라고 단순하게 접근했는데, 그래프를 제공하는 방식이 [1,9]는 주지 않고 [9,1]을 주어서 1과 9의 연결을 표현할 수 있는 방법이라 안된다는 걸 깨달았다. 혼자 이런 반례를 찾고 알고리즘을 고쳐가야하는데 안돌아가면 일단 검색부터 하게 된다,, 멈춰!

그래서 주어진 graphs 행렬을 인접행렬(new_graphs)로 표현한 뒤, 1번 컴퓨터에 대해서만 dfs를 수행하는 식으로 풀었다. 그리고 이 경우에는 visited에 True로 저장된 값이 모두 1번 컴퓨터와 연결된 컴퓨터들이라는 점을 이용해 sum(visited)를 최종 답으로 return했다. 근데 뭐 그냥 computer 변수 하나 두고 값 더해서 계산해도 상관 없을듯!

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
graphs = [list(map(int, input().split())) for _ in range(int(input()))]

new_graphs = [[0]*(n+1) for _ in range(n+1)] # 네트워크 표현용

for g in graphs:
    new_graphs[g[0]][g[1]] = 1
    new_graphs[g[1]][g[0]] = 1

visited = [False]  * (n+1) # 주어진 컴퓨터 번호를 바로 사용하기 위해 + 1

def dfs(v, graphs, visited):
    visited[v] = True

    for i,j in enumerate(new_graphs[v]):
        if j == 1:
            if not visited[i]:
                dfs(i, graphs, visited)

# new_graphs이용해서 1번과 연결된 컴퓨터 개수 세기만 하면 됨 (모든 노드 X)
dfs(1, graphs, visited)
print(sum(visited)-1)

다만 new_graphs가 메모리를 많이 차지하게 되지 않나..? 하는 걱정이... (?)

그리고 백준 채점 서버에서 최대 재귀 깊이는 1,000이 디폴트이다. 따라서 sys.setrecursionlimit() 을 이용해서 이를 바꿔주면 에러 없이 넘어갈 수 있다. (https://help.acmicpc.net/judge/rte/RecursionError)

 

# 프로그래머스 - 타겟 넘버

dfs/bfs 처음 공부할 때 풀어봤던 문제인데 못풀고 구글링했던 문제다. 원랜 다음 숨바꼭질 문제를 먼저 풀려고 했는데, 잘 안풀려서 고민 중이었다. 근데 타겟 넘버 문제가 생각이 나서 여기로 다시 돌아와봤다. 

# bfs
from collections import deque

def solution(numbers, target):

    queue = deque([numbers[0], -numbers[0]])
    count = 2
    
    for n in numbers[1:]:
        for _ in range(count):
            top = queue.popleft()
            queue.append(top+n)
            queue.append(top-n)
        
        count *= 2

    return queue.count(target)

dfs로는 아직도 진짜 모르겠음,, 

 

# 백준 - 숨바꼭질

최단거리를 찾는 문제. 경우의 수가 엄청 많아질 수 있기 때문에 원하는 값을 찾으면 바로 연산을 종료할 수 있는, bfs를 선택했다. 

from collections import deque

N, K = map(int, input().split()) # 수빈 >> 동생

queue = deque([N])
visited = {N:True}
pop_count = 1
answer = 0

if N>=K:
    answer = N-K

else:
    while queue:
        tmp = 0
        answer += 1

        for _ in range(pop_count):
            top = queue.popleft()

            candidates = [top*2, top+1, top-1]

            if K in candidates:
                queue.clear()
                break

            for c in candidates:
                if c>= 0 and c <= 100000 and not visited.get(c):
                    visited[c] = True
                    queue.append(c)
                    tmp += 1
        
        pop_count = tmp

print(answer)

역시나 연산량 컨트롤이 관건이었는데, 내가 놓친 부분들은 다음과 같았다.

1. N >= K 인 케이스
: 처음 짠 코드는 N=K인 케이스를 걸러내지 못했다. 무한루프의 늪으로... 또 작아지는 연산은 -1 밖에 없기 때문에 N > K 인 경우에는 N-K로 바로 연산을 수행할 수 있다.

2. visited
: 처음에는 visited를 빈 리스트로 초기화하고 c를 append, if c not in visited 를 통해 중복 연산을 방지하고자 했다. 그런데 in (not in) 연산 같은 경우에는 리스트 전체를 탐색하기 때문에 시간 복잡도가 N이다. 이 문제를 해결할 수 있는 방법은 두 가지. dict를 활용하거나 [False] * MAX 와 같이 리스트를 초기화해놓고 index로 바로바로 불러다 확인하기.

dict를 사용할 때는 get 연산자를 쓰면 dict에 없는 key 값을 집어넣더라도 error를 리턴하지 않아 코드를 쉽게 짤 수 있다.

3. c>= 0 and c <= 100000
: 문제에서 주어진 조건으로, 이 조건을 걸어주면 N과 M 값이 커졌을 때, 불필요한 연산을 최소한 줄일 수 있다.

 

---

문제를 풀다보니 아무래도 재귀 보다는 좀 더 직관적인 BFS에 손이 더 갔다. 그런데 BFS로만 풀리는 문제가 있으면 어떡하지? 걱정이 되어서 그런 경우가 흔한가 구글링을 해보았다.

PS를 하며 느끼는 DFS와 BFS 선택의 기준

결론은 대부분의 문제는 두 방법 모두로 풀 수 있으나, 한 가지 방법이 확실히 유리한 경우가 종종 있다! 정도. 🤔 많이 풀다보면 뭐가 유리한지 확 감이 온다니, 이 점을 염두에 두고 계속 공부해봐야지.