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)]
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
while queue:
now = queue.popleft()
for i in graph[now]:
if distance[i] == -1:
queue.append(i)
distance[i] = distance[now] + 1
return distance
bfs(graph, x)
isExist = False
for i in range(1, n+1):
if distance[i] == k:
print(i)
isExist = True
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
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
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:
data.append((graph[i][j], 0, i, j))
data.sort()
q = deque(data)
target_s, target_x, target_y = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
while q:
virus, s, x, y = q.popleft()
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) {
if(c == '('){
st.push(c);
}
else {
if(st.empty()){
return false;
}
st.pop();
}
}
return st.empty();
}
string solution(string p) {
if(p.empty()){
return p;
}
string answer = "";
string u = "";
string v = "";
int l = 0, r = 0;
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;
}
}
if(check(u)){
answer = u + solution(v);
}
else {
answer = "(" + solution(v) + ")";
for(int i=1; i < u.length()-1; i++) {
if(u[i] == '('){
answer += ')';
}
else{
answer += '(';
}
}
}
return answer;
}