[이것이 코딩테스트다] [Day4] 탐색 - DFS/BFS

📚 DFS (Depth-First Search)

'깊이 우선 탐색'이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.

특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. 

✅ 동작 과정 ( Stack 이용 )

1️⃣ 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2️⃣ Stack 의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 Stack 에 넣고 방문 처리를 한다.
      방문하지 않은 인접 노드가 없으면 Stack 에서 최상단 노드를 꺼낸다.

3️⃣ 2️⃣번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

* '방문처리' 는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미. 방문처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.

* 일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다.

 

DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며, 탐색을 수행함에 있어서 데이터의 개수가 N인 경우 O(N) 의 시간이 소요된다.

 

다음은 재귀함수를 이용했을 때의 DFS 예제 소스이다.

# DFS 메서드 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end = ' ')
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dsf(graph, i, visited)
            

# DFS 메서드 호출하는 구간

n, m, start = map(int, input().split())

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)

for e in graph:
    e.sort()

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * len(graph)

# 정의된 DFS 메서드 호출
dfs(graph, start, visited)

---

📚 BFS (Breath-First Search)

'너비 우선 탐색'이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘.

DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작하는데 비해, BFS는 그 반대라고 할 수 있다.
BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다.

✅ 동작 과정 ( deque 이용 )

1️⃣ 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2️⃣ 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3️⃣ 2️⃣번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

BFS는 큐 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로 구현함에 있어 deque 라이브러리를 사용하는 것이 좋으며, 탐색을 수행함에 있어서 데이터의 개수가 N인 경우 O(N) 의 시간이 소요된다.

일반적인 경우 실제 수행시간은 DFS보다 좋은 편이다.

 

다음은 BFS 예제 소스이다.

from collections import deque

n, m, start = map(int, input().split())

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)

for e in graph:
    e.sort()

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * len(graph)


# 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[v] = True
                
# 정의된 BFS 메서드 호출
bfs(graph, start, visited)                

---

✅ DFS 와 BFS 정리

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀함수 이용	큐 자료구조 이용

---

⚡ [문제 1] 음료수 얼려먹기 

- 풀이시간 : 30분

 

- 문제풀이

n, m   = map(int, input().split())
graph  = [ list(map(int, input().split())) for _ in range(n)]
result = 0

# 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+1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        return True
    return False


for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            result += 1

print(result)

---

⚡ [문제 2] 미로 탈출

- 풀이시간: 30분

 

- 문제풀이

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

# 이동할 네 방향 정의 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x,y):
    queue = deque((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 ny < 0 or nx >= n 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]

# BFS를 수행한 결과 출력
print(bfs(0,0))
      

---

 

 

※ 해당 포스팅은「이것이 취업을 위한 코딩테스트다(나동빈 저)」책 내용을 바탕으로 작성하였습니다.