(알고리즘)DFS(Depth-First-Search) 깊이 우선 탐색 - 파이썬

---

DFS

---

1. DFS동작 예시

DFS(Depth-First-Search)는 말 그대로 깊은 곳에 있는 노드를 탐색하는 방법이다.

DFS는 재귀함수를 사용하여 깊이 있는노드를 탐색한다.

*재귀함수는 스택과 유사하다.

 

집어 넣은 순서대로 1->2->4->8->5->3->6->7 

---

2. DFS코드 예제(python)

import graphlib

graph=[
  [], #노드가 1부터 시작하므로 비움.
  [2,5,3], #1과 인접한 노드
  [1,4,8], #2와 인접한 노드
  [1,6,7], #3과 인접한 노드
  [2], #4와 인접한 노드
  [1,8], #5와 인접한 노드
  [3,7], #6과 인접한 노드
  [3,6], #7과 인접한 노드
  [2,5] #8과 인접한 노드
]

visited = [False]*len(graph)  #방문 여부 체크 하기 위한 배열


def dfs(v):
  visited[v]=True  #방문한 노드 True로 표시
  print(v, end='  ') #한 줄로 출력
  for i in graph[v]:
    if not visited[i]: #방문한 노드가 아니라면
      dfs(i)  # 함수 실행(재귀함수호출)

dfs(1) #정점 노드인 1부터 시작

 

---

3. DFS 예제 문제 1)

문제

N*M 크기의 얼음트리 있다. 구멍이 뚫려있는 부분은 0, 칸만이가 존재하는 부분은 1로 표시 된다. 구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주하며, 하나의 아이스크림이 만들어 진다. 이때, 얼음 틀의 모양이 주어졌을때, 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성해라. 

---

 

입력

첫 번째 줄에는 얼음틀의 세로 길이 N과 가로길이 M이 주어진다. (1<=N,M<=1000). 각각의 수들은 붙어서 입력으로 주어진다.

---

입력 예시

입력	출력
4 5 00110 00011 11111 00000	3

---

풀이

1. 자신의 위치에서 상,하,좌,우에 또 0 이 있는지 확인해야 된다. (재귀함수 호출)

2. 자신의 위치의 상,하,좌,우가 1 이거나 인덱스를 벗어난 경우를 생각해야 된다.(상,하,좌,우에 아무 숫자가 없는 경우)

---

코드

import sys
N,M = map(int,sys.stdin.readline().split()) 
arr = []

for i in range(N):
#str을 sys로 입력하면 '\n'이 같이 포함되므로 strip()으로 제거해줘야됨.
  a = str(sys.stdin.readline().strip()) 
  arr.append(list(int(i) for i in a))

def dfs(x,y):
  if x<=-1 or x>=N or y<=-1 or y>=M:#범위 벗어난 인덱스 False
    return False
  
  if arr[x][y]==0:
    arr[x][y]=1
    dfs(x-1, y) #상
    dfs(x+1, y) #하
    dfs(x, y-1) #좌
    dfs (x, y+1) #우
    return True #자신 포함 상하좌우의 1들 파악 완료
  return False 

cnt = 0
for i in range(N):
  for j in range(M):
    if dfs(i, j):
      cnt+=1

print(cnt)