[Python] ECC 3주차 정리 - 탐색

# 1. 깊이 우선 탐색(DFS)

• 그래프 완전 탐색 기법 중 하나. 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동한다.
• 재귀 함수로 구현하며 스택 자료구조를 이용한다. 재귀 함수를 이용하는 경우 스택 오버플로에 유의해야 한다.
• 시간복잡도는 O(V+E). (V: 노드 수, E: 에지 수)
• DFS에서는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 리스트가 필요하다.(인접 리스트)
• 또한 DFS의 탐색 방식은 후입선출 특성을 가져 스택을 사용한다. 스택의 성질을 갖는 재귀 함수로 많이 구현한다

 

DFS  핵심 이론

1. DFS를 시작할 노드를 정한 후 사용할 자료구조를 초기화 한다.
   • DFS를 위해 초기에 인접 리스트로 그래프 표현, 방문 리스트 초기화, 시작 노드 스택에 삽입 과정이 필요하다.
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
   • pop을 수행하여 노드를 꺼낸다. 거낸 노드를 탐색 순서에 기록하고 인접 리스트의 인접 노드 (방문하지 않은 노드 모두)를 스택에 삽입하며 방문 리스트를 체크한다.
3. 스택 자료구조에 값이 없을 때까지 반복하기
   • 앞선 과정을 스택 자료구조에 값이 없을 떄까지 반복한다.
   • 이때 이미 다녀각 노드는 방문 리스트를 바탕으로 재삽입하지 않는다.
   • 인접 노드가 없다면 삽입 연산 수행 X

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

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 # visited 리스트에 현재 노드 방문 기록
    for i in A[v]:
        if not visited[i]: # 현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행(재귀 함수 형태)
            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)

• 연결 요소의 개수 == DFS 실행 횟수이다. 즉, 모든 그래프가 연결되어 있다면 DFS는 1번 실행됨.

https://www.acmicpc.net/problem/2023

2023번: 신기한 소수

import sys
sys.setrecursionlimit(10000) # 재귀 최대 깊이 설정
input=sys.stdin.readline
N = int(input())

# 소수 판별 함수
def isPrime(num):
    for i in range(2, int(num/2+1)): # 현재 수%i가 0이면 소수 X
        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, 2): # 짝수라면 더는 탐색 X. 무조건 소수가 아니므로...
            if isPrime(number*10+i): # 소수라면 자릿수 늘리기
                DFS(number*10 + i)

# 일의 자리 소수는 2, 3, 5, 7 이므로 4가지 수에서만 시작
DFS(2)
DFS(3)
DFS(5)
DFS(7)

• 자릿수가 한 개인 소수는 2,3,5,7이므로 이 수부터 탐색을 시작한다.
• 이어서 자릿수가 두 개인 현재 수*10 + a를 계산하여 이 수가 소수인지 판단하고, 소수라면 재귀 함수로 자릿수를 하나 늘린다. 이때 a(코드에서는 i)가 짝수면 무조건 소수가 아니므로 판별도 안함.
• 위 식을 반복해서 현재 수의 자릿수가 N일 때 출력한다.
• 2,3,5,7에서부터 시작하며, 중간 탐색과정에서 소수가 아닌 경우 멈추는 과정(가지치기)이 포함되어 있어 제한 시간 내에 문제를 풀 수 있다.
• isPrime() 함수의 경우, 보통 에라토스테네스의 체를 사용하지만 여기서는 단순 소수 판별 함수로 가능하다.

 

• 에라토스테네스의 체란?
  • 각 수가 가지는 약수가 해당 수의 제곱근을 기준으로 대칭을 이룬다는 특징을 이용한다.
  • 예를 들어, 16의 약수 1,2,4,8,16의 경우 16의 제곱근 4를 기준으로 대칭을 이룬다.
  • 이렇게 하면 시간 복잡도가 O(n)에서 O(n**(1/2)) 로 줄어든다!
  • 즉, 에라토스테네스의 체를 이용하여 소수 판별 여부를 함수로 구현하면 다음과 같다.

# 개선된 소수 판별 함수
def is_prime_number(n):
    end = int(n**(1/2)) # 제곱근을 기준으로 +1 까지만 판별한다.
    for i in range(2, end+1):
        if n % i == 0: # 소수가 아님
            return False
    
    return True

 

https://www.acmicpc.net/problem/13023

13023번: ABCDE

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]: # 방문했던 노드는 탐색 X
            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)

• 주어진 모든 노드에 DFS를 수행하고 재귀의 깊이가 5 이상이면 1, 아니면 0을 출력한다.
• 수행할 때 재귀 호출마다 깊이(depth)를 더한다.
• DFS의 시간 복잡도 O(V+E)이다. N(노드)의 최대 범위가 2,000이므로 모든 노드를 진행했을 때 4,000*2,000으로 제한 시간 내에 가능하다.

 

---

# 2. 너비 우선 탐색(BFS)

• 시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하여 탐색하는 알고리즘.
• FIFO 탐색으로, Queue 자료구조를 이용한다. 
• 시간복잡도는 O(V+E)이다.

BFS 핵심 이론

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
   • DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 체크를 위한 리스트가 필요하고, 그래프를 인접 리스트로 표현한다.
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
   • 큐에서 노드를 꺼내며 인접 노드를 큐에 삽입한다.
   • 이떄 방문 리스트를 체크하여 이미 방문한 노드는 큐에 삽입하지 않으며, 큐에서 꺼낸 노드는 탐색 순서에 기록한다.
3. 큐 자료구조에 값이 없을 때까지 반복하기

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

import sys
from collections import deque
# sys.setrecursionlimit(10000) # 재귀 최대 깊이 설정
input=sys.stdin.readline

N,M, start = map(int, input().split())
A = [[] for _ in range(N+1)]

for _ in range(M):
    s, e = map(int, input().split())
    A[s].append(e) # 양방향 에지
    A[e].append(s)

for i in range(N+1):
    A[i].sort() # 번호가 작은 노드부터 방문하기 위해 정렬하기

def DFS(v):
    print(v, end=' ')
    visited[v] = True
    for i in A[v]:
        if not visited[i]:
            DFS(i)

visited = [False]*(N+1)
DFS(start)

def BFS(v):
    queue = deque()
    queue.append(v)
    visited[v] = True
    while queue:
        now_Node = queue.popleft()
        print(now_Node, end=' ')
        for i in A[now_Node]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

print()
visited = [False]*(N+1) # 리스트 초기화
BFS(start)

• DFS와 BFS 모두 구현하는 문제. 단, 문제에서 작은 번호의 노드부터 탐색한다고 했으므로 인접 노드를 오름차순으로 정렬한다.
• BFS는 큐를 이용하여 구한다는 차이점이 있다.

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

import sys
from collections import deque
# sys.setrecursionlimit(10000) # 재귀 최대 깊이 설정
input=sys.stdin.readline

dx = [0,1,0,-1] # 상하좌우를 탐색하기 위한 리스트 선언
dy = [1,0,-1,0]
N,M= map(int, input().split()) # row, column
A = [[0]*M for _ in range(N)]
visited = [[False]*M for _ in range(N)]

for i in range(N): # 데이터 저장
    numbers = list(input())
    for j in range(M):
        A[i][j] = int(numbers[j])

def BFS(i, j):
    queue = deque()
    queue.append((i, j)) # 시작 노드 삽입
    visited[i][j] = True
    while queue:
        now = queue.popleft()
        for k in range(4): # 상하좌우 탐색
            x = now[0] + dx[k]
            y = now[1] + dy[k]
            if x>= 0 and y >= 0 and x<N and y<M: # 좌표 유효성 검사
                if A[x][y] != 0 and not visited[x][y]: # 이동할 수 있는 칸이면서 방문하지 않은 노드:
                    visited[x][y] = True
                    A[x][y] = A[now[0]][now[1]] + 1 # A 리스트에 depth를 현재 노드의 depth+1로 업데이트
                    queue.append((x, y))

BFS(0,0)
print(A[N-1][M-1])

• 최대 데이터의 크기가 매우 작아 시간 제한 생각 X
• 지나야 하는 칸 수의 최솟값 == 완전 탐색을 진행하며 몇 번째 깊이에서 원하는 값을 찾을 수 있는가 == BFS를 사용하며 최초로 도달했을 때의 깊이를 출력한다.
• BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 다음 깊이로 넘어가므로, DFS보다 적잡하다.

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

import sys
from collections import deque
# sys.setrecursionlimit(10000) # 재귀 최대 깊이 설정
input=sys.stdin.readline

N = int(input())
A = [[] for _ in range(N+1)]

for _ in range(N): # 첫 노드, 인접 노드, 가중치 순으로 입력받으므로 특이..함..
    Data = list(map(int, input().split()))
    index = 0
    S = Data[index]
    index += 1
    while True:
        E = Data[index]
        if E == -1:
            break
        V = Data[index + 1]
        A[S].append((E, V))
        index += 2

distance = [0] *(N+1)
visited = [False]*(N+1)

def BFS(v):
    queue = deque()
    queue.append(v)
    visited[v] = True
    while queue:
        now_Node = queue.popleft()
        for i in A[now_Node]:
            if i in A[now_Node]:
                if not visited[i[0]]:
                    visited[i[0]] = True
                    queue.append(i[0])
                    distance[i[0]] = distance[now_Node] + i[1] # 거리 리스트 업데이트

BFS(1)
Max = 1

for i in range(2, N+1):
    if distance[Max]<distance[i]:
        Max = i # 거리 리스트 값 중 Max 값으로 시작점 재설정

distance = [0]*(N+1)
visited = [False]*(N+1)
BFS(Max) # 새로운 시작점으로 실행
distance.sort()
print(distance[N]) # 리스트에서 가장 큰 수를 정답으로 출력

• 아이디어 : 임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나다.
• 노드에 가중치(에지의 정보, 거리)가 있으므로 노드는 튜플로 선언한다.
• 임의의 노드에서 BFS를 수애하고 탐색할 때 각 노드의 거리를 리스트에 저장한다. 이때 출발하는 노드 n에서, distance[n]은 0이 된다. 나머지 노드에는 현재 노드의 거리 + 에지의 길이를 기록한다.
• 위 과정을 통해 얻은 리스트에서 임의의 노드와 가정 먼 노드를 찾는다. 그 다음 그 노드부터 BFS를 다시 수행한다.
• 위 과정에서 서리 리스트에 저장한 값 중 가장 큰 값을 이 트리의 지름으로 출력한다.
• 주어진 코드는...시간초과가 난다...

# 시간초과 되지 않는 BFS
import sys
from collections import deque
input = sys.stdin.readline

V = int(input())
tree = [[] for _ in range(V+1)]
# 2차원 리스트에 트리 저장(연결 그래프)
for _ in range(V):
    line = list(map(int, input().split()))
    cnt_node = line[0]
    idx = 1
    while line[idx] != -1:
        adj_node, adj_cost = line[idx], line[idx+1]
        tree[cnt_node].append((adj_node, adj_cost))
        idx += 2

def BFS(start):
    q = deque()
    q.append((start, 0))
    visited = [-1]*(V+1)
    visited[start] = 0
    res = [0, 0] # start로부터 가장 먼 거리에 있는 노드와 거리 값
    
    while q:
        cnt_node, cnt_dist = q.popleft()
        
        for adj_node, adj_dist in tree[cnt_node]:
            if visited[adj_node] == -1:
                cal_dist = cnt_dist + adj_dist
                q.append((adj_node, cal_dist))
                visited[adj_node] = cal_dist
                if res[1] < cal_dist:
                    res[0] = adj_node
                    res[1] = cal_dist
        
    return res
    
# 트리 지름 공식 참고
# u-v가 지름이라고 하자. 임의의 점 x에서 가장 먼 거리의 노드 y는
# 반드시 u 또는 v이다. 따라서 y에서 BFS를
# 한번 더 해주면 지름을 구할 수 있다.
point, _ = BFS(1)
print(BFS(point)[1])

• 왜 시간초과가 나지? 다시 공부해봐야겠음...

 

---

# 3. 이진 탐색

• 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 
• 대상 데이터의 중앙값과 찾고자 하는 값을 빅해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.
• 시간 복잡도는 O(logN)으로, 구현 및 원리가 비교적 간단하 부분 문제로 많이 사용한다.

이진 탐색 핵심 이론(오름차순의 경우, 내림차순은 조건 반대로)

1. 현재 데이터의 중앙값을 선택한다.
2. 중앙값 > 타깃 데이터일때 중앙값을 기준으로 왼쪽 데이터셋을 선택
3. 중앙값 < 타깃 데이터일때 중앙값을 기준으로 오른쪽 데이터셋을 선택
4. 위 과정을 반복하다가 중앙값 == 타깃데이터일 때 탐색 종료

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

N = int(input())
A = list(map(int, input().split()))
A.sort()
M = int(input())
target_list = list(map(int, input().split()))

for i in range(M):
    find = False
    target = target_list[i] # 찾아야 하는 수
    # 이진 탐색 시작
    start = 0
    end = len(A) - 1
    while start <= end:
        midi = int((start+end)/2) # 중간 인덱스
        midv = A[midi] # 중앙값
        if midv > target: # 중앙값이 타겟값보다 크면
            end = midi - 1 # 종료 인덱스 = 중간 인덱스 -1
        elif midv < target: # 중앙값이 타겟값보다 작으면
            start = midi + 1 # 시작 인덱스 = 중간 인덱스 + 1
        else: # 찾은 경우 반복문 종료
            find = True
            break
    if find:
        print(1)
    else:
        print(0)

• 이진 탐색은 정렬을 가정하므로 정렬 함수 sort()를 사용했다.
• 데이터 정렬까지 고려하여 N의 최대 범위가 100,000이므로 O(nlogn)의 시간복잡도로 해결 가능하다.

https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

N, M = map(int, input().split())
A = list(map(int, input().split()))
start = 0
end = 0

for i in A:
    if start <i:
        start = i # 레슨 최댓 값을 시작 인덱스로 저장
    end += i # 모든 레습의 총합을 종료 인덱스로 저장

while start <= end:
    middle = int((start + end) / 2)
    sum = 0
    count = 0
    for i in range(N): # 중간 값으로 모든 레슨을 저장할 수 있는지 확인
        if sum + A[i] > middle: # sum + 현재 레슨 시간 > 중간 인덱스인 경우
            count +=1 # count +=1, sum 리셋
            sum = 0
            # 현재 블루레이에 저장할 수 없어 새로운 블루레이로 교체
        sum += A[i]   # sum += 현재 레슨 시간
    if sum != 0: # 마지막 블루레이가 필요하므로 count 값 올리기
        count += 1
    if count > M: # 중간 인덱스 값으로 모든 레슨 저장 불가능
        start = middle + 1
    else: # 중간 인덱스 값으로 모든 레슨 저장 가능. 단, 최솟값을 찾으므로 탐색은 계속 수행
        end = middle - 1

print(start)

• 블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 한다는 조건으로 이진 탐색 알고리즘을 사용한다.
• 모두 저장할 수 있다면 블루레이의 크기를 줄이고, 없다면 블루레이의 크기를 늘린다.
• 이진 탐색의 시작 인덱스는 최대 레슨 시간, 종료 인덱스는 레슨 시간을 모두 합한 값이다. 블루레이 개수가 3일 때 블루레이 크기의 최솟값을 이진 탐색으로 찾는다.
• 시작 인덱스>종료 인덱스일 때까지 이진 탐색을 수행한다.
• 예를 들어, 1번째 탐색의 중앙값이 27(9+45/2)일 때는 크기가 27인 블루레이에 강의를 저장할 수 있는 지 확인하는 것이다. 주어진 블루레이 개수 3장 이내에 모든 레슨이 저장 가능하므로 종료 인덱스를 수정 후 다시 탐색을 수행한다.
• 중간 for()문에서 sum이 블루레이 크기(중앙값)을 넘을때마다 coutn하여 모든 레슨을 돈다. 이것으로 중앙값으로 모든 레슨이 저장 가능한지 확인한는 것!
• 저장할 수 없으면 시작 인덱스를 수정한 후 탐색을 수행한다.
• 이진 탐색을 반복하다가 시작 인덱스 > 종료 인덱스를 종료할 때의 시작 인덱스 값이 답이 된다.

https://www.acmicpc.net/problem/1300

1300번: K번째 수

N = int(input())
K = int(input())
start = 1
end = K
ans = 0

# 이진 탐색 수행
while start <= end:
    middle = int((start+end)/2)
    cnt = 0
    # 중앙값보다 작은 수 계산
    for i in range(1, N+1):
        # cnt에 중앙 인덱스를 i로 나눈 값과 N 중 작은 값을 더함
        cnt += min(int(middle/i), N) # 작은 수 카운트 핵심 로직
    if cnt < K: # 현재 중앙값보다 작은 수의 개수가 K보다 작음
        start = middle + 1
    else: # 현재 중앙값보다 작은 수의 개수가 K보다 크거나 같음
        ans = middle
        end = middle -1

print(ans)

• K의 범위가 1~min(10^9, N)이므로 이진 탐색을 사용한다. 이진 탐색으로 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄인다.
• 즉, 작은 수의 개수가 K-1개인 중앙값이 정답이다.
• 이차원 배열에서, 각 행에서 중앙값보다 작거나 같은 수의 개수는 중앙값을 각 행의 첫 번째 값으로 나눈 값이다. 이때 나눈 값이 N보다 크면 N(모든 수가 중앙값보다 작다)으로 정한다. 코드로 하면 min(int(middle/i),N)
• 이렇게 구한 각 열의 값을 합했을 때, 이 cnt가 K보다 크거나 같으면 종료 인덱스 = 중앙값 -1로 업데이트 한다. 즉, 이때의 중앙값 middle보다 큰 범위에 정답이 존재한다.
• 반대로 cnt가 K보다 작으면 시작 인덱스 = 중앙값 + 1로 한다. cnt란 현재 값(middle)보다 작거나 같은 수의 개수이므로, cnt가 더 큰 오른쪽 배열에서 탐색을 진행해야 하므로!

---

# 회고

 

어렵다...해석을 보면 이해가 가는데 직접 생각해서 구현하려면 힘들다.

특히 DFS는 정말 많이 보이는데 좀 많이 풀어보고 문제를 볼때 DFS다! 라고 외칠 수 있어야 하지 않을까