DFS(Depth-First Search)란?

스택 자료구조 (or 재귀함수) 이용

코드 정리

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

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 표현 (index 0은 사용 X)
visit = [False] * 9

dfs(graph,1,visit)

문제 1 - 음료수 얼려 먹기

풀이

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 = []
cnt = 0

for _ in range(m):
    graph.append(list(map(int,input())))

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