[이코테 python] Ch.5.1 DFS (+ 음료수 얼려 먹기 문제)

5.1.1  DFS (Depth-First-Search) 알고리즘

 

 

깊이 우선 탐색 : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

 

 

DFS 는 최대한 깊숙이 노드들을 방문한 후, 다시 돌아가 다른 경로를 탐색하는 알고리즘을 말한다.

 

따라서, DFS 는 스택 자료구조를 이용하여 구현할 수 있다.

 

 

 

 

 

DFS 동작 과정은 다음과 같다.

 

 

1) 스택에 탐색 노드를 삽입하고, 방문값을 true 로 바꾼다.

 

2) 스택의 최상단 노드에서 방문하지 않은 인접노드를 스택에 넣고, 방문값을 true 로 바꾼다.

 

3) 스택의 최상단 노드에서 방분하지 않은 인접노드가 없으면, 단순히 최상단 노드를 꺼낸다.

 

4) 스택에 값이 없을 때까지 2, 3 번의 과정을 반복한다.

 

 

 

 

---

 

 

5.1.2  DFS 알고리즘 특징

 

 

 

DFS 알고리즘은 스택 자료구조를 이용하여 구현된다.

 

 

하지만, 실제 알고리즘을 구현할 때, 

 

스택을 사용하지 않고 재귀함수를 이용하면 더 간단하게 알고리즘을 구현할 수 있다.

 

 

 

다음은 재귀함수를 이용하여 DFS 를 구현한 코드이다.

 

 

 

# 재귀함수를 이용한 DFS 알고리즘

# 그래프 정보를 2차원 리스트로 표현
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 방문 처리 1차원 리스트
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)

 

 

 

 

graph

 

 

: 인덱스가 0인 노드는 비워두고 사용하지 않는다.

 

 

visited = [False]*9

 

 

: 인덱스가 0인 노드를 사용하지 않았으므로, 9개의 1차원 리스트를 생성한다.

 

 

 

 

재귀함수를 이용하여 DFS 를 구현하면, 
데이터의 개수가 N 개 일 때, 시간 복잡도는 O(N) 이다.

 

 

 

 

---

 

 

5.1.3  DFS 알고리즘 예시 - 음료수 얼려 먹기

 

 

풀이시간 : 30분 / 제한시간 : 1초 / 메모리 제한 : 128MB

 

 

 

문제 )
N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1호 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

 

입력 조건 )
첫째 줄에 얼음 틀의 세로 길이 N 과 가로 길이 M 이 주어진다. (1 <= N, M <= 1000)
둘째 줄부터 N+1 번째 줄까지 얼음 틀의 형태가 주어진다.
이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

 

출력 조건 )
한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

 

 

 

 

1) 문제 해결 아이디어

 

 

DFS 를 이용하여 문제를 해결할 수 있다.

 

1) 상, 하, 좌, 우를 탐색하여, 값이 0 인 지점 중 아직 방문하지 않은 지점을 방문한다.

 

2) 1의 과정을 계속 반복하여 모든 지점을 방문한다.

 

3) 1, 2의 과정 중에서 방문하지 않은 지점의 개수를 센다.

 

 

 

2) 문제 해결 코드 ( Python )

 

 

# 음료수 얼려 먹기 문제 (DFS)

# N x M 개수 입력
n, m = map(int, input().split())

# N x M 2차원 리스트 입력
graph = []
for i in range(n):
    # 띄어쓰기 없이 입력
    graph.append(list(map(int, input())))

# DFS 로 노드 방문
def dfs(x,y):

    # 그래프 벗어나는 경우 종료
    if x<=-1 or y<=-1 or x>=n or y>=n:
        return False

    # 방문하지 않은 인접 노드 방문
    if graph[x][y] == 0:
        graph[x][y] == 1
        dfs(x, y+1)
        dfs(x, y-1)
        dfs(x-1, y)
        dfs(x+1, y)
        return True
    return False


# 만들 수 있는 아이스크림 개수 세기
count = 0
for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            count += 1

print(count)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

나동빈 '이것이 코딩 테스트다 with 파이썬' 책을 기반으로 작성하였습니다.

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC