DFS

WooHyeong·2022년 10월 4일
0

Algorithm

목록 보기
1/41

DFS

  • Depth First Search, 깊이 우선 탐색

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

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

  • DFS의 동작 과정
    1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
    2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
    3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

    • '방문 처리'는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.
def dfs(graph, start, visited):

    visited[start] = True

    print(start, end = " ")

    for i in graph[start]:
        if visited[i] == False:
            dfs(graph, i, visited)  
            
graph = [[],
         [2,3,8],
         [1,7],
         [1,4,5],
         [3,5],
         [3,4],
         [7],
         [2,6,8],
         [1,7]]
         
visited = [False]*9
dfs(graph, 1, visited) # dfs(그래프, 시작지점, 방문처리

연습 문제

'''
DFS/BFS 실전 문제 3. 음료수 얼려 먹기
N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때 생성되는 총 아이스크림의 개수를 구하여라.

Ex)
4 5
00110
00011
11111
00000

result = 8
'''
import sys
n, m = map(int, sys.stdin.readline().split())
frames = []
result = 0
for i in range(n):
    frames.append(list(map(int, input())))

# def 사용해서 재귀로 풀어보는게 맞을듯 dfs 로 풀도록 하자.
def dfs(x,y):
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    if frames[x][y] == 0:
        frames[x][y] = 1 #방문한 곳이기 때문에 1로 처리하여 재방문 x로 만듦
        dfs(x-1,y) #인덱스가 범위를 벗어나더라도 위에 조건문에서 처리해주기 때문에 괜찮음 그래서 필요했구만 위 조건문은
        dfs(x, y-1)
        dfs(x+1,y)
        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)
profile
화이링~!

0개의 댓글