WEEK. 02 2022.04.08 TIL

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 뜻함. 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 존재.

스택 자료구조

먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조로, 입구와 출구가 동일한 형태로 스택을 시각화할 수 있음.

큐 자료구조

먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조로, 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있음.

유클리드 호제법

두 자연수 A, B에 대해 (A>B) A를 B로 나눈 나머지를 R이라고 할 때, A와 B의 최대 공약수는 B와 R의 최대공약수과 같음.

def uh(a, b): 
    print(a, b)
    if a%b == 0:
        print(b)
        return

    return uh(b, a%b)

DFS(Depth-First Search)

• DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작은 다음과 같음.

  1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 함.
  2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.
  3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복함.

인접한 노드가 여러개일 수 있기 때문에 어떤 노드부터 방문할지의 기준이 필요하고, 이는 문제에 따라 달라질 수 있고, 방문 순서가 상관 없을 경우도 존재.

graph = [[], # 각 노드들의 인접 노드 번호
        [2, 3, 8],
        [1, 7],
        [1, 4, 5],
        [3, 5],
        [3, 4],
        [7],
        [2, 6, 8],
        [1, 7]]

visited = [False] * 9 # 예제에서 1번 노드부터 시작했기 때문에 0 index는 비워둠.

def dfs_prac(i, graph, visited):
    visited[i] = True # 현재 노드에 대해 방문 처리
    print(i, '번째 노드를 방문하였습니다.')
    for j in graph[i]: # 현재 노드들의 인접 노드들을 방문하기 위한 반복문
        if not visited[j]: # 인접 노드가 방문 처리가 안되어 있으면 해당 노드로 방문
            dfs_prac(j, graph, visited) #스택 자료구조의 용도로 재귀함수 사용

dfs_prac(1, graph, visited)

BFS(Breadth-First Search)

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 ex) 특정 목적에서의 최단 거리
• BFS는 큐 자료구조를 이용하며, 구체적인 동작은 다음과 같음.

  1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 함.
  2) 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 함.
  3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복.

def bfs_prac(i, graph, visited):
    queue = deque([i]) # 큐 생성하여 첫번째 탐색 노드 삽입
    visited[i] = True # 삽입한 노드 방문 체크

    while queue: # 큐의 노드가 모두 없어질때까지
        v = queue.popleft() # 큐에서 노드 하나를 뽑아 출력
        print(v, end=' ')
        for j in graph[v]: # 출력한 노드의 인접 노드들에 대해 탐색
            if not visited[j]: # 방문체크 확인
                queue.append(j) # 방문하지 않았으면 큐에 노드 삽입
                visited[j] = True # 해당 노드 방문체크

bfs_prac(1, graph, visited)

예제 - 음료수 얼려 먹기

• N x M 크기의 얼음틀에서 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시
• 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주
  

• 특정 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 0이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문
• 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문할 수 있음.
• 모든 노드에 대해 1~2번의 과정을 반복하며, 방문하지 않은 지점의 수를 카운트.

# dfs로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y):
    # 맵의 주어진 범위를 벗어나는 경우에는 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    # 현재 노드를 아직 방문하지 않았다면 
    if graph[x][y] == 0:
        # 해당 노드 방문 처리
        graph[x][y] = 1
        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출하여 방문
        dfs(x-1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)

        return True

    return False

n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# 모든 노드(위치)에 대해 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        # 현재 위치에서 dfs 수행
        if dfs(i, j) == True:
            result += 1 # 순차적으로 탐색 시 이미 방문 처리가 되었다는 것은 다른 노드의 탐색으로 인해 이미 방문 처리가 되었음을 의미하므로 처음 방문하는 노드에서 dfs를 호출하여 탐색이 끝난 후 True를 반환하면 카운트 함.

print(result) # 정답 출력

미로 탈출 - BFS

• N x M 크기의 직사각형 형태의 미로에 괴물이 존재하고, 이를 피해 탈출 해야함. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시
• 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수. (최단 거리 탐색)

  1) BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색
  2) 상, 하, 좌, 우로 연결된 모든 노드로의 거리가 1로 동일함. 따라서, (1,1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하여 해결

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우) 좌표를 행, 열로 표현하다 보니 (0,0)에서 위로 올라갈 경우 -1행 즉 (-1, 0)이 되므로 이렇게 적용한듯
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    # 큐(Qeueu) 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x,y))
    # 큐가 빌 때까지 반복하기
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 4가지 방향으로의 위치 확인. 그 후 괴물이 있거나(graph[nx][ny] == 0) 맵의 범위를 벗어나면 (가로=6, 세로=5) 중단. i = (0, 1, 2, 3) 각 값이 방향을 의미함.
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 찾기 공간을 벗어난 경우 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 벽인 경우 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1 # 출발하는 위치와 도착하는 위치를 포함하기 때문에 출발하는 경우 1로 표시되어 있으므로 새로운 방향으로 탐색 시 1을 더해준다.
                queue.append((nx, ny)) # 탐색을 위해 큐에 해당 위치를 삽입
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1]

- 생각 정리

이진 탐색

• 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
• 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정

파이썬 이진 탐색 라이브러리

• bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
• bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환

from bisect import bisect_left, bisect_right
# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
	right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index
    
# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3))

파라메트릭 서치(Parametric Search)

• 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법.
  ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
• 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있음.
• 탐색 범위가 엄청 크면 이진 탐색을 적용해야 함.