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 함수 호출
dfs(graph, 1, visited)

graph의 깊이를 우선적으로 탐색한다.

음료수 얼려먹기

서로 연결되어있는 연결요소의 갯수가 몇개인지 구하면 된다. 방문처리가 이루어지는 요소에 대해서만 카운트하면 알 수 있다.

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 줍변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문.
2. 방문한 지점에서 상, 하, 좌, 우를 살펴 보면서 방문으르 진행하는 과정을 반복하면, 연결된 모든 지점을 방문.
3. 모든 노드에 대하여 1 ~2번 과정을 반복하며, 방문하지 않은 지점의 수를 카운트.

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
  graph.append(list(map(int, input())))

# 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

# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
  for j in range(m):
    # 현재 위치에서 DFS수행
    if dfs(i, j) == True:
      result +=1

print(result)