Chapter 09. 그래프 기본 탐색 알고리즘

그래프 기본 탐색 알고리즘 (기초 문제풀이)

혼자 힘으로 풀어 보기

DFS와 BFS: https://www.acmicpc.net/problem/1260

문제 제목: DFS와 BFS
문제 난이도: 하(Easy)
문제 유형: DFS, BFS
추천 풀이 시간: 30분

문제 풀이 핵심 아이디어

• 기본적인 형태의 그래프를 단순히 DFS와 BFS로 탐색합니다.
• 이 문제에서는 "정점 번호가 작은 것"을 먼저 방문해야 합니다.
• 모든 노드와 간선을 차례대로 조회하여 O(N+M)의 시간 복잡도로 문제를 해결해야 합니다.
• 국내 코딩 테스트 합격을 위해서는 이 문제를 매우 빠르게 풀 수 있도록 숙달할 필요가 있습니다.
• 큐(Queue) 구현을 위해 collections 라이브러리의 deque를 사용합니다.
• 예시) 정점 개수 = 4, 간선 개수 = 5, 시작 정점 번호 = 1
  

소스 코드

# 덱을 사용하여서 BFS를 구현
from collections import deque

def dfs(v):
    print(v, end=' ')
    visited[v] = True
    for e in adj[v]:
        if not(visited[e]):
            dfs(e)

def bfs(v):
    q = deque([v])
    while q:
        v = q.popleft()
        if not(visited[v]):
            visited[v] = True
            printf(v, end=' ')
            for e in adj[v]:
                if not visited[e]:
                    q.append(e)

# 정점 개수, 간선 개수, 시작 정점 번호
n, m, v = map(int, input().split())
adj = [[] for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

# 정점 번호가 작은 것을 먼저 방문 하기 위해서 정렬
for e in adj:
    e.sort()

# DFS, BFS를 진행하기 전에 모든 정점을 False로 초기화
visited = [False] * (n+1)
dfs(v)
print()
visited = [False] * (n+1)
bfs(v)

혼자 힘으로 풀어 보기

숨바꼭질: https://www.acmicpc.net/problem/1697

문제 제목: 숨바꼭질
문제 난이도: 하(Easy)
문제 유형: BFS
추천 풀이 시간: 30분

문제 풀이 핵심 아이디어

• 특정 위치까지 이동하는 최단 시간을 계산해야 하는 문제입니다.
• 이동 시간이 모두 1초로 동일하므로, 간단히 BFS를 이용하여 해결할 수 있습니다.
• 큐(Queue) 구현을 위해 collections 라이브러리의 deque를 사용합니다.
• 5에서 12로 가는 최단 시간은 다음과 같이 계산할 수 있습니다.
  

소스코드

from collections import deque

MAX = 100001
n, k = map(int, input().split())
array = [0] * MAX 

def bfs():
    q = deque([n])
    while q:
        now_pos = q.popleft()
        if now_pos == k:
            return array[now_pos]
        for next_pos in (now_pos-1, now_pos+1, now_pos*2):
            if 0 <= next_pos < MAX and not array[next_pos]:
                # 이전 정점에 +1을 함으로써 새로운 정점까지의 시간을 구할수 있음.
                array[next_pos] = array[now_pos] +1
                # q에 next_pos를 넣어줌으로써 반복적으로 진행.
                q.append(next_pos)

print(bfs())

그래프 기본 탐색 알고리즘 (핵심 유형 문제풀이)

혼자 힘으로 풀어 보기

바이러스: https://www.acmicpc.net/problem/2606

문제 제목: 바이러스
문제 난이도: 하(Easy)
문제 유형: DFS, BFS
추천 풀이 시간: 30분

문제 풀이 핵심 아이디어

• 단순히 시작 정점에서부터 도달할 수 있는 노드의 수를 계산하는 문제입니다.
• 따라서 DFS혹은 BFS를 이용하여 방문하게 되는 노드의 개수를 계산하면 됩니다.
• 컴퓨터의 수(정점의 수)가 적으므로, DFS를 이용해 빠르게 문제를 푸는 것이 유리합니다.
• 예시) 정점 개수 = 7, 간선 개수 = 6, 시작 정점 번호 = 1
  

소스코드

n = int(input())
m = int(input())
adj = [[] for _ in range(n+1)]
visited = [False] * (n+1)
count =  0

for _ in range(m):
    x, y = map(int, input().spilt())
    adj[x].append(y)
    adj[y].append(x)

def dfs(now_pos):
    global count
    # 방문할 때마다 count를 1 증가.
    count += 1
    visited[now_pos] = True
    for next_pos in adj[now_pos]:
        if not visited[next_pos]:
            dfs(next_pos)

dfs(1)
print(count-1)

혼자 힘으로 풀어 보기

유기농 배추: https://www.acmicpc.net/problem/1012

문제 제목: 유기농 배추
문제 난이도: 하(Easy)
문제 유형: DFS, BFS
추천 풀이 시간: 30분

문제 풀이 핵심 아이디어

• 연결 요소의 개수를 세는 문제입니다.
• 모든 정점에 대하여 DFS및 BFS를 수행하고, 한 번 방문한 정점은 다시 확인하지 않습니다.
• 전체적으로 DFS 및 BFS를 수행한 총 횟수를 계산합니다.
• DFS 및 BFS 응용 문제 중에서 출제 비중이 매우 높은 유형 중 하나입니다.
• DFS로 문제를 푸는 경우, sys라이브러리 setrecursionlimit() 함수 설정을 해줄 필요가 있습니다.
• 예시를 확인해 봅시다.
  

소스코드

import sys
sys.setrecursionlimit(100000)
# 비효율적인 재귀를 막기위해서 재귀의 횟수를 제한

def dfs(x, y):
    visited[x][y] = True
    # 상하좌우로 탐색을 하기 위함.
    directions = [(-1, 0), (1,0), (0,-1), (0,1)]
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        # next x와 next y가 이차원 배열에 속해 있다면 계속 해서 진행.
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        # 방문하지 않았으며, 값이 1인 곳만 처리하도록 함.
        if array[nx][ny] and not visited[nx][ny]:
            dfs(nx, ny)

for _ in range(int(input())):
    m, n, k = map(int, input().split())
    array = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    for _ in range(k):
        y, x = map(int, input().split())
        array[x][y] = 1
    result = 0
    for i in range(n):
        for j in range(m):
            # 방문되지 않으며, 1인 경우에만 탐색을 진행.
            if array[i][j] and not visited[i][j]:
                dfs(i, j)
                result += 1
    print(result)            

혼자 힘으로 풀어 보기

효율적인 해킹: https://www.acmicpc.net/problem/1325

문제 제목: 효율적인 해킹
문제 난이도: 하(Easy)
문제 유형: DFS, BFS
추천 풀이 시간: 30분

문제 풀이 핵심 아이디어

• 모든 정점에 대하여 DFS 및 BFS를 수행합니다.
• DFS 혹은 BFS를 수행할 때마다 방문하게 되는 노드의 개수를 계산하면 됩니다.
• 가장 노드의 개수가 크게 되는 시작 정점을 출력합니다.
• 예시) 정점 개수 = 5, 간선 개수 = 4
  

소스코드

from collections import deque

n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, input().split())
    adj[y].append(x)

def bfs(v):
    q = deque([v])
    visited = [False] * (n+1)
    visited[v] = True
    count = 1
    while q:
        v = q.popleft()
        for e in adj[v]:
            if not visited[e]:
            # 방문 하였을 때에만, 1을 증가.
                q.append(e)
                visited[e] = True
                count += 1
        return count            

result = []
max_value = -1

# 모든 정점에 대한 간선의 개수를 구함.
for i in range(1, n+1):
    c = bfs(i)
    # 가장 큰 정점의 개수를 가진 값을 반환하기 위함.
    if c > max_value:
        result = [i]
        max_value = c
    elif c == max_value:
        result.appent(i)
        max_value = c

for e in result:
    print(e, end=" ")