DFS ( Depth First Search)
깊이우선 탐색
깊은 부분을 우선적으로 탐색하는 알고리즘
스택 자료구조 혹은 재귀함수를 이용한다.
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
def dfs(graph, v, visited):
visited[v] = True
print(v,end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i , visited)
dfs(graph,1, visited)
Python
복사
BFS(Breadth First Search)
넓이우선탐색. 가까운 노드부터 우선적으로 탐색하는 알고리즘
큐 자료구조를 사용한다.
1.
탐색 시작 노드를 큐에 삽입하고 방문처리
2.
큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 큐에 삽입하고 방문처리
3.
더 이상 2번의 과정을 수행할 수 없을때까지 반복
from collections import deque
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False] * 9
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
# until queue is empty
while queue:
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
bfs(graph, 1, visited)
Python
복사
ex) 음료수 얼려먹기 (DFS)
N*M크기의 얼음 틀이 있다. 구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려있는 부분끼리 상하좌우로 붙어있는 경우 서로 연결되어있는 것으로 간주한다.
얼음 틀의 모양이 주어졌을때 생성되는 총 아이스크림 개수를 구해라.
map(int, ...)
•
map()은 두 개의 인자를 받는 함수입니다: 첫 번째 인자는 변환할 함수, 두 번째 인자는 변환할 iterable(반복 가능한 객체)입니다.
•
int는 문자열을 정수로 변환하는 함수입니다.
•
예를 들어, map(int, ['1', '2', '3', '4'])는 ['1', '2', '3', '4']의 각 요소를 int로 변환하여 [1, 2, 3, 4]를 생성합니다.
•
map()은 변환된 값을 반환하는 map 객체를 생성하므로, 이를 list()로 감싸야 리스트로 변환할 수 있습니다.
n,m = map(int, input().split())
# N*M 2차원 배열 입력받기
graph = []
for i in range(n):
graph.append(list(map(int,input())))
result = 0
def dfs(x,y):
if x < 0 or x>=n or y<0 or y>=m:
return False
else:
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
else:
return False
for i in range(n):
for j in range(m):
if dfs(i,j) == True:
# 연결된 모든 노드들은 이미 1로 바뀌어있기때문에 중복 count가 발생하지 않음
result+=1
print(result)
Python
복사
0인 노드를 찾고, DFS를 통해서 해당 노드와 인접한 모든 0인 노드를 찾아서 방문처리함.
N*M개의 노드에 대해서 모두 DFS 수행
ex) 미로찾기 (BFS)
N*M크기의 직사각형 미로에 갇혀있다. 미로에는 여러마리의 괴물이 있다.
현재 위치는 (1,1)이며 미로의 출구는 (N,M)이다. 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어있다. 탈출하기 위해서 움직여야하는 최소 칸의 개수를 구해라. (시작칸과 마지막 칸 포함)
from collections import deque
n,m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int,input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x,y):
queue = deque()
queue.append((x,y))
while queue:
x,y = queue.popleft()
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
queue.append((nx,ny))
return graph[n-1][m-1]
print(bfs(0,0))
Python
복사
