꼭 필요한 자료구조 기초
탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.
그 중 DFS/BFS를 대표적인 알고리즘으로 꼽을 수 있는데 이를 이해하려면 스택, 큐, 재귀함수를 알아야한다.
스택, 큐
스택: 후입선출
*파이썬의 append()와 pop()함수로 삽입, 삭제
큐: 선입선출
from collection import deque queue = deque() queue.append(5) queue.append(6) queue.popleft()👉파이썬에서는 collection 모듈에서 제공하는 deque 자료구조를 활용하자.
재귀함수
재귀함수 자기 자신을 다시 호출하는 함수이다. 이때 재귀함수 없이 해결할 수 있는 정료 조건을 꼭 명시해야 한다. 무한 루프에 빠지지 않게 하기 위해서이다.
✨재귀함수는 내부적으로 스택 자료구조와 동일하다. 따라서 스택 자료구조를 활용해야하는 상당수 알고리즘은 재귀 함수를 이용해서 표현할 수 있다.
- 코드가 점화식을 그대로 표현하여 직관적이다.
- 무한루프, 스택오버플로우를 주의해야 한다.
탐색 알고리즘 DFS/BFS
그래프 표현
프로그래밍에서 그래프는 인접 행렬, 인접 리스트 2가지 방식으로 표현할 수 있다.
🎉인접 행렬: 2차원 배열로 각 노드가 연결된 형태를 기록. 연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성.
INF = 999999999 #무한의 비용 선언 graph = [ [0, 7, 5] [7, 0, INF] [5, INF, 0] ] print(graph)
🎉인접 리스트: 리스트로 그래프의 연결 관계를 표현.
- C++, JAVA의 경우 별도의 라이브러리를 제공하지만 Python에서는 기본 리스트 자료형이 append()와 메소드를 제공. 즉 단순히 2차원 리스트를 이용.
# 행이 3개인 2차원 리스트로 인접 리스트 표현 graph = [[] for _ in range(3)] # 노드 0에 연결된 노드 정보 저장(노드, 거리) graph[0].append((1, 7)) graph[0].append((2, 5)) # 노드 1에 연결된 노드 정보 저장(노드, 거리) graph[1].append((0, 7)) # 노드 2에 연결된 노드 정보 저장(노드, 거리) graph[1].append((0, 5)) print(graph)
💡위 두 방식은 어떤 차이가 있을까?
메모리 측면에서 인접 행렬 방식은 모든 관계를 저장, 인접 리스트는 연결된 정보만 저장
👉 특정한 노드의 연결 유무: 인접 행렬이 더 빠름
👉 특정한 노드와 연결된 모든 인접 노드를 순회: 인접 리스트가 더 빠름
DFS 깊이 우선 탐색
그래프에서 깊은 부분을 먼저 탐색하는 알고리즘
- 스택 자료구조에 기초한다는 점에서 구현이 간단
- 데이터가 n개인 경우 O(n)의 시간이 소요
- 최대한 멀리있는 노드를 우선으로 탐색
#DFS 메서드 정의
def dfs(graph, v, visited):
#현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
#현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
#정의된 DFS 함수 호출
dfs(graph, 1, visited)BFS 너비 우선 탐색
그래프에서 가까운 노드부터 탐색하는 알고리즘
- 큐 자료구조를 이용하여 인접한 노드를 반복적으로 큐에 넣음
- deque라이브러리 사용
- 일반적인 경우 수행시간은 DFS보다 좋은 편
from collections import deque
#BFS정의
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
#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
#정의된 DFS 함수 호출
bfs(graph, 1, visited)실전문제
✨음료수 얼려 먹기
n, m = map(int, input().split())
ice_graph = []
for _ in range(n):
ice_graph.append(map(int, input()))
def dfs(x, y):
#범위를 넘어가면 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
if ice_graph[x][y] == 0: #방문하지 않았다면
ice_graph[x][y] = 1 #방문 처리하고 상하좌우 재귀호출
dfs(x+1, y)
dfs(x-1, y)
dfs(x, y+1)
dfs(x, y-1)
return False #이미 1이라면 종료
cnt = 0
#dfs 반복문으로 실행
for i in range(n):
for j in range(m):
if dfs(n, m) == True:
cnt += 1
print(cnt)모든 노드를 방문해야 하니 깊이 우선 탐색을 사용했다.
재귀 호출로 상하좌우를 탐색하고 모든 조건을 통과해 True를 리턴 받으면 cnt에 1을 더하여 마지막으로 총 cnt 값을 출력하는 코드이다.
✨미로 탈출
from collections import deque
n, m = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input())))
#4방향 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
#BFS 소스코드
def bfs(x, y):
queue = deque()
queue.append((x, y)) #시작점 인큐
#큐가 빌 때까지 반복
while queue:
x, y = queue.popleft() #x, y에 각각 1 대입
for i in range(4): #4방향에 반복
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny > 0 or nx >= n or ny >= m: #범위 밖이면 무시
continue
if graph[x][y] == 0: #0이면 무시
continue
if graph[x][y] == 1:
graph[nx][ny] = graph[x][y] +1 #기존 x,y 좌표의 값에 1을 더한 값을 대입
queue.append((nx, ny)) #인큐
return graph[n-1][m-1] #반복문이 끝나면 n,m 좌표의 값을 리턴(인덱스는 0부터 시작이므로 -1)
print(bfs(0, 0)) 이 문제는 최단 거리를 구해야 하므로 bfs 너비 우선 탐색을 사용했다.
다음 노드로 이동할 때 그 노드의 데이터 값을 +1하며 마지막 종점에 달했을 때 데이터 값을 리턴하면 이동한 횟수를 리턴하게 되는 것이다.
