DFS

정의 및  장단점

DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

연결되어 있는 노드를 깊숙히 바고 들어간다. 그 노드의 끝을 보고 다시 돌아오면서 연결되어있는 다른 노드를 찾을시  이번엔 그 노드를 

끝까지 파고든다. 스택을 기초로 하고 있다.

 

출처: https://iq.opengenus.org/dfs-vs-bfs/

 

구현방법

스택, 재귀함수를 이용하여 구현한다. 스택을 기초로 하지만 직접적으로 사용하지는 않음.

O(N)의 시간이 소요.

 

문제 예시

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

 

입력예시:

00110

00011

11111

00000

 

아이스크림의 갯수를 세시오.

import sys
myMap=[]
move=[(-1,0),(1,0),(0,1),(0,-1)]

N,M= map(int,sys.stdin.readline().split())

visited=[[True]*N for _ in range(M)]

for i in range(M):
    temp = (sys.stdin.readline().split())
    myMap.append(list(map(int,temp[0])))


print(myMap)

def search(start_x,start_y):
    if start_x >= M or start_y >= N or start_x < 0 or start_y < 0:  #맵을 벗어나는지 체크
        return 0
    if visited[start_x][start_y]==True and myMap[start_x][start_y]==0: #방문,빈틀 체크
        visited[start_x][start_y]=False
        for i in move:
            next_x = start_x+i[0]
            next_y = start_y+i[1]
            search(next_x,next_y)
        return 1    	
    else:
        return 0


count=0
for i in range(M):
    for j in range(N):
        count +=  search(i,j) #최초실행함수에서만 결국 1을 리턴받으니 리턴값의 합은 아이스크림의 수
print(count)

 

 

 

https://yunzae.tistory.com/60

스택(Stack)