Search Algorithm
- 탐색 == 많은 데이터 중 원하는 데이터만 찾아내는 과정
- 대표적인 그래프 탐색 알고리즘 == DFS & BFS
- 자주 나오는 유형
Stack
- FILO : 먼저 입력되는 데이터가 나중에 나감
- 입구와 출구가 동일한 형태로 시각화 가능 ex)상자 쌓기
- list = []
- 삽입 : 맨 마지막에 넣기 append(x) → O(1)
- 삭제 : 맨 마지막에 있는 원소 삭제 pop() → O(1)
Queue
- FIFO : 먼저 들어온 데이터가 먼저 나감
- 입구와 출구가 모두 뚫린 터널과 같은 형태로 시각화 가능
- from collections import deque → 파이썬에서는 deque 라이브러리 사용 queue = deque()
- 삽입 : append() → O(1)
- 삭제 : popleft() → O(1)
- reverse : 역순으로 바꾸기
재귀 함수
- 자기 자신을 다시 호출하는 함수
- 파이썬에서는 재귀 깊이 제한이 있기 때문에 무한 반복되지 않고 오류 메시지 뜸
- 재귀함수의 종료 조건
- 함수를 스택에 넣었다가 빼는 것처럼 실제로 함수들이 스택 프레임에 담김
- 가장 마지막에 호출된 함수부터 차례대로 종료됨 (FILO)
- 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있음
- 모든 재귀 함수는 반복문을 이용해서 동일한 기능 구현 가능
DFS
- Depth-fist Search (깊이 우선 탐색)
- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조(or 재귀함수) 사용
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있으면, 그 노드를 스택에 넣고 방문 처리
- 방문하지 않은 인접 노드 없으면 스택에서 최상단 노드 꺼냄
- 2~3의 과정 더 이상 반복할 수 없으면 끝
- 방문 기준이 필요함 ex)번호가 낮은 인접 노드
def dfs(graph, v, visited):
# 현재 노드 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
BFS
- Breadth-first Search (너비 우선 탐색)
- 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 큐 자료구조 사용
- 탐색 시작 노드 큐에 넣고 방문처리
- 큐에서 노드 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드 모두 큐에 삽입하고 방문처리
- 2번 과정 수행할 수 없을 때까지 반복
- 방문 기준이 필요함 ex)번호가 낮은 인접 노드
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
# 큐에서 원소 하나 뽑아서 출력
v = queue.popleft()
print(v, end=' ')
# 아직 방문하지 않은 인접한 원소들 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
#15 특정 거리의 도시 찾기
from collections import deque
# 도시 수, 도로 수, 최단 거리, 출발 도시 번호
n, m, k, x = map(int, input().split())
# 각 노드가 연결된 정보
graph = [[] for _ in range(n+1)] # 1~N번
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
# 모든 도시(노드)까지 걸리는 최단 거리 초기화
distance = [-1] * (n + 1)
# 최단 거리 함수
def bfs(graph, start):
queue = deque([start]) # 큐 구현
distance[start] = 0 # 자기 자신까지의 거리는 항상 0
# 큐가 빌 때까지 반복
while queue:
now = queue.popleft()
# 해당 도시(노드)와 인접하고 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[now]:
if distance[i] == -1:
queue.append(i)
distance[i] = distance[now] + 1 # 1씩 추가해서 최단거리 저장
return distance
# 함수 실행
bfs(graph, x)
isExist = False # 최단 거리가 K인 도시 존재 여부
for i in range(1, n+1): # 1~N번까지의 도시 중에서
if distance[i] == k: # 최단 거리가 K인 도시 출력
print(i)
isExist = True
# 최단 거리가 K인 도시가 없으면 -1 출력
if isExist == False:
print(-1)
#16 연구소
import sys
input = lambda : sys.stdin.readline().strip()
n, m = map(int, input())
graph = []
temp = [[0]*m for _ in range(n)]
for _ in range(n):
graph.append(list(map(int, input())))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
result = 0
#바이러스 퍼지는 함수
def virus(x,y):
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if 0 <= nx < n and 0 <= ny < m:
if temp[nx][ny] == 0: #빈 공간인 경우
temp[nx][ny] = 2
virus(nx, ny)
#안전한 영역 계산하기
def score():
score = 0
for i in range(n):
for j in range(m):
if temp[i][j] == 0:
score+=1
return score
#깊이 우선 탐색(DFS를 이용해 울타리를 설치하면서 안전영역의 크기를 계산)
#count : 울타리 갯수
def dfs(count):
global result
if count == 3:
for i in range(n):
for j in range(m):
temp[i][j] = graph[i][j]
for i in range(n):
for j in range(m):
if temp[i][j] == 2:
virus(i, j)
result = max(result, score())
return
#빈공간에 울타리 설치
#DFS 이용해 울타리 설치 가능한 모든경우의 수 탐색
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
graph[i][j] = 1
count+=1
dfs(count)
graph[i][j] = 0
count-=1
dfs(0)
print(result)
#17 경쟁적 전염
from collections import deque
n, k = map(int, input().split())
graph = [] #전체 보드 정보를 담는 리스트
data = [] # 바이러스에 대한 정보를 담는 리스트
for i in range(n):
# 보드 정보를 한 줄 단위로 입력
graph.append(list(map(int, input().split())))
for j in range(n):
#해당 위치에 바이러스가 존재하는 경우
if graph[i][j] != 0:
# (바이러스 종류, 시간, 위치 X, 위치 Y) 삽입
data.append((graph[i][j], 0, i, j))
# 정렬 이후에 큐로 옮기기(낮은 번호의 바이러스가 먼저 증식하므로)
data.sort()
q = deque(data)
target_s, target_x, target_y = map(int, input().split())
# 바이러스가 퍼져나갈 수 있는 4가지 위치
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# BFS 진행
while q:
virus, s, x, y = q.popleft()
# 정확히 s초가 지나거나, 큐가 빌 때까지 반복
if s == target_s:
break
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 해당 위치로 이동할 수 있는 경우
if 0 <= nx and nx < n and 0 <= ny and ny < n:
# 아직 방문하지 않은 위치라면, 그 위치에 바이러스 넣기
if graph[nx][ny] == 0:
graph[nx][ny] = virus
q.append((virus, s + 1, nx, ny))
print(graph[target_x - 1][target_y - 1])
#18 괄호 변환
#include <string>
#include <vector>
#include <stack>
using namespace std;
bool check(string p) {
stack<char> st;
for(auto c : p) {
// 왼쪽 괄호 문자열일 경우, 스택에 넣고 오른쪽 괄호 문자열일 경우, 스택에 있는 골호를 꺼낸다.
// 단, 괄호가 비어있을 경우, false를 반환한다.
if(c == '('){
st.push(c);
}
else {
if(st.empty()){
return false;
}
st.pop();
}
}
// 스택이 비어있을 경우, 올바른 문자열이므로 true를 반환하도록 하고
// 스택이 비어있지 않을 경우, 올바르지 않은 문자열이므로 false를 반환한다.
return st.empty();
}
string solution(string p) {
// 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환한다.
if(p.empty()){
return p;
}
string answer = "";
string u = "";
string v = "";
int l = 0, r = 0;
// 2. 균형잡힌 괄호 문자열 u, v로 분리
for(int i = 0; i < p.length(); i++) {
if(p[i] == '(') {
l++;
}
else {
r++;
}
if(l == r) {
u = p.substr(0, i+1);
v = p.substr(i+1);
break;
}
}
// 3. 올바른 문자열일 경우, 문자열 v에 대해 1단계 부터 수행한 문자열을 u에 이어 붙인다.
if(check(u)){
answer = u + solution(v);
}
// 4. 올바른 괄호 문자열이 아닐 경우,
else {
// 4-1. 빈 문자열에 첫 번째 문자로 ( 를 붙인다.
// 4-2. 문자열 v에 대해 1단계 부터 수행한 문자열을 이어 붙인다.
// 4-3. ) 를 다시 붙인다.
answer = "(" + solution(v) + ")";
// 4-4. u의 첫 번째와 마지막 문자를 제거해야 하므로 i를 1부터 확인하도록 하고
// (u의 길이 - 1) 보다 작은 i 만 확인한다.
for(int i=1; i < u.length()-1; i++) {
// 나머지 문자열의 괄호 방향을 뒤집어서 붙인다.
if(u[i] == '('){
answer += ')';
}
else{
answer += '(';
}
}
}
// 4-5. 생성된 문자열을 반환한다.
return answer;
}