그래프 탐색 알고리즘 DFS & BFS, Backtracking(백트래킹) (2)

DFS(Depth-First Search)

출처 : 이코테, dfs 알고리즘 파이썬

- DFS : 깊이우선 탐색
- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- DFS는 스택 자료구조(혹은 재귀 함수)를 이용 1. 탐색 시작 노드를 스택에 삽입 후 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리,
방문하지 않은 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

+ ) Backtracking(백트래킹)

- 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기에 정답을 찾아가는 범용적 알고리즘

- 탐색에서는 이 길이 아닌 것 같으면 왔던 길로 되돌아와 다른 선택지로 감

- 재귀로 보통 구현, 재귀 함수가 호출되고 조건에 맞지 않으면 종료되고 그전에 호출된 재귀로 돌아옴

- 안 되는 조건은 없애면서 탐색하기 때문에 시간복잡도가 선형적으로 증가할 법한 문제에서 백트래킹을 적용하면 시간복잡도를 줄일 수 있음

BFS(Breadth-First Search)

출처 : 이코테, bfs 알고리즘 파이썬

- BFS : 너비우선 탐색
- 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- BFS는 큐 자료구조를 이용

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

이코테 문제1 - 음료수 얼려 먹기 (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())
   
   graph = []
   for i in range(n):
   	graph.append(list(map(int, input())))
    
  result = 0
  for i in range(n):
  	for j in range(m):
    	if dfs(i,j) == True:
        	reuslt += 1
  print(result)

 

- 얼음틀을 그래프 형식으로 연결해 볼 수 있음
- 앞 뒤 양 옆 살펴보며 방문처리하며 해결

<나의 문제>
- 어떤 방식으로 문제를 해결하려고 고민하지 않고,
- 재귀적으로 어떻게 호출하면 되는 지에 대해서만 생각함
- 기본 dfs 코드에 이 문제를 무조건적으로 넣으려고 함

이코테 문제2 - 미로탈출 (BFS 이용)

출처 : 이코테

#이코테 정답코드
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]
         

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]

print(bfs(0,0))

 

- 튜플 형식으로 위치 저장
- 미로를 지나갈 때마다 값 1씩 증가

<나의 문제>
- 거리의 수를 count로 계산하려고 함
- 재귀적으로 어떻게 호출하면 되는 지에 대해서만 생각함
- 기본 bfs 코드에 이 문제를 무조건적으로 넣으려고 함