[BAEKJOON] 그래프탐색 뽀개기 | 파이썬 | 백준 Lv24. DFS와 BFS 문제풀이

BAEKJOON 백준 코딩테스트 단계별로 풀어보기 > LEVEL24. DFS와 BFS https://www.acmicpc.net/step/24

DFS와 BFS 단계

 

그래프(Graph)

정점(node)와 간선(edge)으로 이루어진 자료구조의 일종으로 특정 노드를 시작으로 모든 노드를 한번씩 방문하는 것을 그래프 탐색이라고 한다.

트리는 그래프의 일종으로 정점마다 간선이 없을수도 있는 그래프와 달리 모든 노드가 연결되어있는 연결 그래프로 루트 노드와 부모, 자식 노드의 개념이 있다.

 

 

 

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

루트 노드(특정 노드)에서 시작하여 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법

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

모든 노드를 탐색하고자할 때 사용하며 BFS보다 간단하지만 검색 속도 자체는 BFS에 비해 느리다.

* 어떤 노드를 방문했는지 노드 방문 검사를 해야하며 스택(후입선출)을 이용하여 방문 노드 정보를 저장한다.

 

 

BFS(너비우선탐색, Breadth-First Search)

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법

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

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

* 어떤 노드를 방문했는지 노드 방문 검사를 해야하며큐(선입선출)을 이용하여 방문 노드 정보를 저장한다.

 

 

주제별로 처음부터 다져나가기에는 프로그래머스보다 백준 단계별 문제 풀이가 더 좋은 듯하다

 

 

1260. DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하라. 더 이상 방문할 노드가 없는 경우 종료한다.

 

메모리 32468KB / 756ms

먼저 입력받는 부분의 코드와 결과 출력 코드

import collections

# 입력
n, m, v = map(int, input().split())
graph = collections.defaultdict(list)

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()
    
# 출력
for node in dfs_recursive(graph, v, []): # dfs(graph, v)
    print(node, end=' ')
print()
for node in bfs(graph, v):
    print(node, end=' ')

그래프를 이중배열로 구현하는 경우도 봤는데 나는 딕셔너리로 공부해서 그런지 그래프가 사전 형태로 주어지는게 다루기도 쉽고 이해하기도 쉽다. 그래서 파이썬으로 그래프 구현할 때 collections.defaultdict를 사용하여 모든 노드를 키로 두고 각 키에 대해 연결된 노드 리스트를 값으로 갖는다.

예를 들어 입력이

4 5 1
1 2
1 3
1 4
2 4
3 4

이렇게 들어오면 

{
    1: [2, 3, 4]
    2: [1, 4]
    3: [1, 4]
    4: [1, 2, 3]
}

이런 모습의 사전이 만들어진다

 

DFS 재귀 버전

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

DFS 비재귀 버전

def dfs(graph, start):
    visited = []
    stack = [start]
    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack.extend(graph[n])
    return visited

 

BFS

def bfs(graph, start):
    visited = []
    queue = [start]
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
    return visited

pop(0) 대신 deque로 구현하여 popleft()를 사용해도 되지 않을까 싶다.

 

 

2606. 바이러스

한 컴퓨터가 웜 바이러스에 걸리면 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 어느 날 1번 컴퓨터가 웜바이러스에 걸렸다. 컴퓨터 수와 네트워크 상 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하여라

 

메모리 32360KB / 시간 100ms

import collections

n = int(input())
m = int(input())
graph = collections.defaultdict(list)

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def bfs(graph, start):
    visited = []
    queue = [start]
    
    while queue:
        node = queue.pop()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
            
    return visited
        

print(len(bfs(graph, 1))-1)

모든 노드를 거칠 필요 없어 기준 노드 중심으로 연결되어있는 노드만 확인하면 됨으로 BFS를 이용해 풀었다. 사실 연결되어 있으면 모든 노드를 탐색하게 되고 결국 1번 노드가 포함된 연결 그래프를 찾는 문제가 되어서 DFS를 이용해서 풀어도 되지 않았을까 싶긴 한데 암튼 난 BFS 이용함

기본 BFS 코드에서 딱히 수정한 것은 없고 1번 노드를 시작 노드로 연결 그래프를 찾아 그 그래프에 속한 노드 수를 정답으로 하였다.

(1을 빼주는 이유는 1번 노드를 빼기 위해)

 

 

2667. 단지번호붙이기

정사각형 모양의 지도가 있고 1은 집이 있는 곳, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임에 단지를 정의하고 번호를 붙이려 한다. 연결되어있다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말하며 대각선상 있는 집은 연결된 것이 아니다. 지도를 입력하여 단지수를 출력하고 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하라

 

메모리 30846KB / 시간 128ms

주어진 지도를 입력받는 부분

n = int(input())
lines = []
apts = []
for i in range(n):
    lines.append((list(input())))
    
cnt = 0 # 총 아파트 수
for i in range(n):
    for j in range(n):
        if lines[i][j] == '1':
            cnt += 1 
            apts.append((i, j))
            
total_visited = [] # 아파트 방문 체크
answer = []
apts.sort(key=lambda x: (x[0], x[1])) # 가로 세로 붙어있는 것을 확인하기위해 정렬

집이 있는 곳의 인덱스 정보만 저장하여 그래프를 구성하였다. 먼저 입력 형태처럼 2차원 배열로 입력받은 다음 집이 있는 1인 경우에만 리스트 apts에 해당 위치의 인덱스 정보(i, j)를 저장한다. 이후 인덱스를 이용하여 가로, 세로 인접한 경우를 판단하기 위해 i, j 순으로 정렬을 해준다.

 

DFS 코드 활용

def dfs_apt(graph):
    stack = [graph[0]]
    visited = [graph[0]]
    
    while stack:
        node = stack.pop()
        for g in graph:
            if ((g[0] == node[0]) and (abs(g[1]-node[1]) == 1)) or ((g[1] == node[1]) and (abs(g[0]-node[0]) == 1)):
                # i가 같고 j가 1 차이남 -> 가로로 붙어있음, j가 같고 i가 1 차이남 -> 세로로 붙어있음
                if g not in visited:
                    stack.append(g)
                    visited.append(g)

    return visited

위의 문제와 마찬가지로 주어진 그래프 내 연결그래프 수와 각 그래프마다 속한 노드의 개수를 묻는 문제이다.

먼저 단지를 구성하는 세로나 가로로 인접한 노드들을 찾기 위해 배열의 인덱스를 이용하였다. 집이 있는 특정 노드 기준 같은 i열일 때 j행만 1 차이나는 곳은 세로로 인접한 경우, 같은 j행일 때 i열만 1씩 차이나는 곳은 가로로 인접한 경우라고 생각하였다.

노드 방문 검사 전 인덱스를 검사하여 주어진 곳과 인접한 곳인지 판단한 후 둘다 통과하면 방문 여부를 체크하고 다음 순서로 진행한다.

 

DFS를 이용하여 그래프 수를 세는 코드

while True:
    if len(total_visited) == cnt:
        break
    tmp = (dfs_apt(apts)) # 한 단지 내 아파트들
    total_visited.extend(tmp) # 전체 방문여부에 체크
    answer.append(len(tmp)) # 답에 단지 내 아파트 수 추가
    apts = list(set(apts) - set(total_visited)) # 남은 아파트들

비연결 그래프를 모두 탐색하여 연결 그래프를 세기 위해서는 그래프에 속한 모든 노드들에 대해 방문 검사가 이뤄져야 한다. DFS의 경우 한 연결그래프의 모든 노드를 방문하고 나면 끝이 남으로 다른 연결그래프의 노드를 다시 시작 노드로 전달하여 DFS를 해야 한다.

나는 total_visited 배열을 두고 한번의 DFS가 끝나고 반환되는 방문 노드들을 제외시켜 남은 미방문 노드들을 다시 DFS를 돌게 함으로써 이를 구현하였다.

그리고 이렇게 해서 total_visitied의 길이가 전체 노드 수와 같아지만(모든 노드를 방문하면) 끝이 난다.

total_visited와 apts를 계속 집합 연산으로 계산하는게 아니라 DFS 메서드에도 인자로 visited를 전달하고 반환값으로 받으면 되지 않을까 싶기도 하다.

나중에 해봐야할 듯

 

정답 출력 부분, 백준은 출력 형태 검사도 조금 까다로워서 마지막 정답 출력까지 잘 작성해야한다ㅠ

print(len(answer))
answer.sort()
for a in answer:
    print(a)

 

 

1012. 유기농 배추

차세대 영농인 한나는 강원도 고랭지에 유기농 배추를 재배하기로 했다. 한나는 해충 방지를 위해 배추흰지렁이를 구입하기로 결심하였다. 배추흰지렁이는 한 마리라도 살고 있으면 인접한 다른 배추로도 이동할 수 있어 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우 서로 인접해있는 것이다.

한나는 재배하는 땅 곳곳에 배추를 심어두었다. 배추들이 인접하여 모여있는 곳에 배추흰지렁이 한 마리만 있으면 됨으로 서로 인접해있는 배추들이 몇 군데 퍼져있는지 조사하여 필요한 지렁이 수를 알아내야 한다.

 

이 또한  연결그래프 수를 세는 문제로 앞선 문제들과 비슷한 유형이다. 똑같이 DFS로 풀었다.

 

메모리 30864KB / 시간 2304ms

입력과 정답 출력 부분

test = int(input())
answer = []
for i in range(test):
    graph = []
    m, n, k = map(int, input().split())
    for i in range(k):
        i, j = map(int, input().split())
        graph.append((i, j))
        graph.sort(key=lambda x:(x[0], x[1]))
    answer.append(solution(graph, m, n, k))
    
for a in answer:
    print(a)

위의 문제와 똑같이 풀었다. 배추가 있을 때(값이 1일 때)의 인덱스 정보를 배열에 저장하여 그래프를 만든다. 인접 여부를 인덱스로 확인할 것임으로 인덱스로 정렬해준다.

 

 

연결 그래프를 찾기 위한 DFS 활용 메서드

def dfs_feild(graph):
    visited = [graph[0]]
    stack = [graph[0]]
    while stack:
        node = stack.pop()
        for g in graph:
            if ((g[0]==node[0]) and (abs(g[1]-node[1])==1)) or ((g[1]==node[1]) and (abs(g[0]-node[0])==1)):
                if g not in visited:
                    visited.append(g)
                    stack.append(g)
    return visited

위와 마찬가지로 방문 여부와 인접 여부 확인 후 DFS를 진행한다.

 

탐색하지 않은 노드를 찾아 DFS를 호출하는 solution 메서드

def solution(graph, w, h, k):
    cnt = 0
    while graph:
        tmp = dfs_feild(graph)
        graph = list(set(graph) - set(tmp)) # 남은 아파트들
        cnt += 1
       
    return cnt

total_visited 배열을 따로 두지 않고 방문한 노드들을 그래프에서 제거하여 모든 노드를 돌도록 했다. 한번 DFS가 완료될 때마다 하나의 배추 뭉텅이가 있는 것임으로 카운트도 증가

 

---

기본 그래프 탐색 코드를 활용하고 조금만 머리쓰면 풀 수 있던 문제들이라 탐색 코드를 이해하기 좋은 문제들이었다.

프로그래머스의 경우 문제 난이도가 정해져있긴 하지만 바로 응용으로 가다보니 살짝 버거운 감이 있었는데

백준에서 단계별로 풀어보니 코드 이해가 더 잘된 듯 하다.

 

7문제가 더 있는데 차차 추가할 예정!