탐색

• 탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘이다.
• 주어진 데이터의 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요하다.
• 실제 코딩 테스트 문제의 기본이 되는 알고리즘이므로 직접 구현해 원리를 완벽하게 이해하는 것이 중요하다.

05-1 깊이 우선 탐색

• 깊이 우선 탐색 DFS는 그래프 완전 탐색 기법 중 하나이다.
• 그래프의 시작 노드에서 출발하여, 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후, 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
• 기능: 그래프 완전 탐색
• 특징: 재귀 함수로 구현, 스택 자료구조 이용
• 시간 복잡도(노드 수 V, 에지 수 E): O(V+E)
• 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이요하므로 스택 오버플로에 유의해야 한다.
• 응용 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.

[깊이 우선 탐색의 핵심 이론]

• DFS는 한 번 방문한 노드를 다시 방문하면 안 되기 때문에, 노드 방문 여부를 체크할 리스트가 필요하며, 그래프는 인접 리스트로 표현하자.
• DFS의 탐색 방식은 후입선출 특성을 가지므로 스택을 사용하자.
• 하지만, DFS 구현은 스택보다 스택 성질을 갖는 재귀 함수로 많이 구현한다.
• 대부분의 DFS 문제는 재귀 함수로 구현하도록 하자.

예시) 1 -> 2 -> 5
                 -> 6
1 -> 3 -> 4 -> 6

1. DFS를 시작할 노드를 정한 후, 사용할 자료구조 초기화하기

• DFS를 위해 필요한 초기 작업
  (1) 인접 리스트로 그래프 표현하기
  (2) 방문 리스트 초기화 하기
  (3) 시작 노드 스택에 삽입하기
• 스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 리스트를 체크하면 T, F, F, F, F, F가 된다.

2. 스택에서 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

• 이제 pop을 수행하여 노드를 꺼낸다.
• 꺼낸 노드를 탐색 순서에 기입한다.
• 인접 리스트의 인접 노드를 스택에 삽입하며 방문 리스트를 체크한다.
• 방문 리스트는 T, T, T, F, F, F가 된다.
• 탐색 순서: 1

3. 스택 자료구조에 값이 없을 때까지 반복하기

• 앞선 과정을 스택 자료구조에 값이 없을 때까지 반복한다.
• 이때 이미 다녀간 노드는 방문 리스트를 바탕으로 재삽입하지 않는 것이 핵심이다.
• 탐색 순서: 1 -> 3 -> 4 -> 6 -> 2 -> 5

📌 문제 023) 연결 요소의 개수 구하기

시간 제한 3초, 실버 V, 백준 11724번

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

6 5 # 노드 개수, 에지 개수
1 2
2 5
5 1
3 4
4 6

출력

첫째 줄에 연결 요소의 개수를 출력한다.

2

1단계 문제 분석

• 노드의 최대 개수가 1,000이므로 시간 복잡도 N^2이하의 알고리즘을 모두 사용할 수 있다.
• 연결 요소는 에지로 연결된 노드의 집합이다.
• 한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단할 수 있다.
• 그래프를 인접 리스트로 저장하고 방문 리스트도 초기화한다.

1. 방향이 없는 그래프이기 때문에 양쪽 방향으로 에지를 모두 저장한다.

• 인접 리스트
  1 -> 2 / 5
  2 -> 1 / 5
  3 -> 4
  4 -> 3 / 6
  5 -> 2 / 1
  6 -> 4

• 방문 리스트
  1 2 3 4 5 6
  F F F F F F

2. 임의의 시작점에서 DFS를 수행한다. 현재의 경우는 1을 시작점으로 정했다. 탐색을 마친 후, 방문한 곳은 1, 2, 5가 된다.

• 방문 리스트
  1 2 3 4 5 6
  T T F F T F

• 탐색 순서: 1 -> 2 -> 5

3. 아직 방문하지 않은 노드가 있으므로 시작점을 다시 정해 탐색을 진행한다. 현재의 경우 3으로 시작점을 정하고, 3, 4, 6 순서로 탐색을 마쳤다. 모든 노드를 방문했으니 전체 탐색을 종료한다.

• 방문 리스트
  1 2 3 4 5 6
  T T T T T T

• 탐색 순서: 1 -> 2 -> 5 -> 3 -> 4 -> 6 -> 종료

4. 1~3 과정을 통해 총 2번의 DFS가 진행되었다는 것을 알 수 있다. 즉, 연결 요소 개수는 2개이다.

• 모든 노드를 탐색하여 탐색 종료 -> DFS 총 2회 수행 -> 즉, 연결 요소 개수 = 2
• 만약, 그래프가 모두 연결되어 있었다면 DFS는 1번 실행되었을 것이다.
• 다시 말해, 모든 노드를 탐색하는 데 실행한 DFS의 실행 횟수가 곧 연결 요소 개수와 같다.

2단계 슈도 코드

n(노드 개수) m(에지 개수)
A(그래프 데이터 저장 인접 리스트) 초기화
visited(방문 기록 리스트) 초기화

# DFS 구현
DFS:
	visited 리스트에 현재 노드 방문 기록
    현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행(재귀 함수 형태)
    
for m의 개수만큼 반복:
	A 인접 리스트에 그래프 데이터 저장
    
for n의 개수만큼 반복:
	if 방문하지 않은 노드가 있으면:
    	연결 요소 개수 값 1 증가
        DFS 실행

연결 요소 개수 값 출력

3단계 코드 구현

import sys
sys.setrecursionlimit(10000) # 재귀 호출의 최대 깊이 제한을 설정하는 함수
input = sys.stdin.readline
n, m = map(int, input().split())
A = [[] for _ in range(n+1)]
visited = [False] * (n+1)

def DFS(v):
    visited[v] = True
    for i in A[v]: # ex) 1에 연결된 2와 5 모두 DFS 수행
        if not visited[i]:
            DFS(i)
            
for _ in range(m): # 그래프를 인접 리스트로 저장하기
    s, e = map(int, input().split())
    A[s].append(e) # 양방향 에지이므로 양쪽에 에지를 더하기
    A[e].append(s)
    
count = 0

for i in range(1, n+1):
    if not visited[i]:
        count += 1
        DFS(i)

print(count)

📌 문제 024) 신기한 소수 찾기

시간 제한 2초, 골드 V, 백준 2023번

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.
7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.
수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

4 # 자릿수 N

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

1단계 문제 분석

• DFS는 재귀 함수의 형태이다.
• 재귀 함수를 잘 이해하면 문제 조건에 맞도록 코드를 수정하기 쉽다.
• 이 문제는 재귀 함수에 자릿수 개념을 붙여 구현한다.

[문제 핵심]

• 소수는 약수가 1과 자기 자신인 수를 말한다.
• 우선 자릿수가 한 개인 소수는 2, 3, 5, 7이므로 이 수부터 탐색을 시작한다.
• 4, 6, 8, 9를 제외한 가지치기 방식을 적용한 것이다.
• 이어서 자릿수가 두 개인 현재 수 * 10 + a를 계산하여 이 수가 소수인지 판단하고, 소수라면 재귀 함수로 자릿수를 하나 늘린다.
• 단, a가 짝수인 경우는 항상 2를 약수로 가지므로 가지치기로 a가 짝수인 경우를 제외한다. (1, 3, 5, 7, 9)
• 이런 방식으로 자릿수를 N까지 확장했을 때 그 값이 소수라면 해당 값을 출력한다.
• 즉, N자리까지 재귀 함수 형태로 탐색한다.
• 소수가 아닌 경우 멈추는 경우를 넣어 제한 시간 내에 문제를 풀 수 있게 한다.
• 소수를 판별하는 방법은 보통 에라토스테네스의 체를 사용하지만, 이 문제는 단순한 소수 판별 함수를 사용해도 된다.

2단계 슈도 코드

N(자릿수)
#소수 구하기 함수
for i를 2~(현재 수/2)+1까지 반복:
	if 현재 수 % i가 0이면:
    	return 소수가 아님

#DFS 구현
DFS(숫자):
	if 자릿수 == N:
    	현재 수 출력
    else
    	for i를 1~9 반복:
        	if i를 뒤에 붙인 새로운 수가 홀수이면서 소수일 때 # 소수 구하기 함수 사용
            	DFS(수 * 10 + 뒤에 붙는 수) 실행
                
DFS 실행(숫자 2, 3, 5, 7로 탐색 시작)

3단계 코드 구현

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N = int(input())

def isPrime(num):
    for i in range(2, int(num / 2 + 1)):
        if num % i == 0:
            return False
    return True
            
def DFS(number):
    if len(str(number)) == N:
        print(number)
    
    else:
        for i in range(1, 10):
            if i % 2 == 0: # 짝수라면 더는 탐색 불필요
                continue
            if isPrime(number * 10 + i): # 소수라면 자릿수 늘림
                DFS(number * 10 + i)
            
# 일의 자리 소수는 2, 3, 5, 7이므로 4가지 수에서만 시작   
DFS(2)
DFS(3)
DFS(5)
DFS(7)

📌 문제 025) 친구 관계 파악하기

시간 제한 2초, 골드 V, 백준 13023번

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.
  위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

8 8 # 노드 개수, 에지 개수
1 7
3 7
4 7
3 4
4 6
3 5
0 4
2 7

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

1

1단계 문제 분석

• N의 최대 범위가 2,000이므로 알고리즘의 시간 복잡도를 고려할 때 좀 더 자유롭다.
• 문제에서 요구하는 A, B, C, D, E의 관계는 재귀 함수의 형태와 비슷하다.
• 주어진 모든 노드에 DFS를 수행하고, 재귀의 깊이가 5 이상(5개의 노드가 재귀 형태로 연결)이면 1, 아니라면 0으로 출력한다.
• DFS의 시간 복잡도는 O(V+E)이므로 최대 4,000, 모든 노드를 진행했을 때 4,000 * 2,000, 즉, 8,000,000이므로 DFS를 사용해도 제한 시간 내에 문제를 풀 수 있다.

1. 그래프 데이터를 인접 리스트로 저장한다.

• 인접 리스트
  0 -> 4
  1 -> 7
  2 -> 7
  3 -> 7 / 4 / 5
  4 -> 7 / 4 / 6 / 0
  5 -> 3
  6 -> 4
  7 -> 1 / 3 / 4 / 2

2. 모든 노드에서 DFS를 수행한다. 수행할 때 재귀 호출마다 깊이를 더한다. 깊이가 5가 되면 1을 출력하고 프로그램을 종료한다.

3. 모든 노드를 돌아도 1이 출력되지 않았다면 0을 출력한다.

2단계 슈도 코드

N(노드 개수) M(에지 개수)
A(그래프 데이터 저장 인접 리스트)
visited(방문 기록 저장 리스트)
arrive(도착 확인 변수)

# DFS 구현(현재 노드, 깊이):
	if 깊이가 5:
    	arrive = true;
        함수 종료
    방문 리스트에 현재 노드 방문 기록
    현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행 # 호출마다 depth는 1씩 증가
    
for M의 개수만큼 반복:
	A 인접 리스트에 그래프 데이터 저장

for N의 개수만큼 반복:
	노드마다 DFS 실행
    if(arrive) 반복문 종료 # depth가 5에 도달한 적이 있다면

if arrive: 1 출력
else: 0 출력

3단계 코드 구현

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N, M = map(int, input().split())
arrive = False
A = [[] for _ in range(N+1)]
visited = [False] * (N+1)

def DFS(now, depth):
    global arrive
    if depth == 5: # 깊이가 5가 되면 종료
        arrive = True
        return

    visited[now] = True
    for i in A[now]:
        if not visited[i]:
            DFS(i, depth + 1) # 재귀 호출마다 깊이 증가

    visited[now] = False
    
for _ in range(M): # 그래프를 인접 리스트로 저장하기
    s, e = map(int, input().split())
    A[s].append(e) # 양방향 에지이므로 양쪽에 에지를 더하기
    A[e].append(s)
    
for i in range(N):
    DFS(i, 1)
    if arrive:
        break

if arrive:
    print(1)
else:
    print(0)