[제주코딩베이스캠프] 눈떠보니 코딩테스트 전날 | 문제5. 그림자 연결!

def 깊이우선탐색(graph,start):
	방문=[]
    # 너비우선탐색 : 큐 이용 / 깊이우선탐색 : 스택 이용
    stack=[start]
    
    while stack:
    	n=stack.pop()
        if n not in 방문:
        	방문.append(n)
        	차집합 = graph[n]-set(방문)
            stack+=차집합
            
   	return 방문
    
  깊이우선탐색(graph,100)
 
 # 작은값 순회
 def 깊이우선탐색(graph,start):
	방문=[]
    # 너비우선탐색 : 큐 이용 / 깊이우선탐색 : 스택 이용
    stack=[start]
    
    while stack:
    	n=stack.pop()
        if n not in 방문:
        	방문.append(n)
        	차집합 = graph[n]-set(방문)
            if len(차집합)==0:
            	방문+=stack
                break
              
            stack.append(min(차집합))
            
   	return 방문
    
  # 큰 값 순회
 def 깊이우선탐색(graph,start):
	방문=[]
    # 너비우선탐색 : 큐 이용 / 깊이우선탐색 : 스택 이용
    stack=[start]
    
    while stack:
    	n=stack.pop()
        if n not in 방문:
        	방문.append(n)
        	차집합 = graph[n]-set(방문)
            if len(차집합)==0:
            	방문+=stack
                break
              
            stack.append(max(차집합))
            
   	return 방문

---

DFS , Depth First Search (깊이 우선 탐색) - stack

> 현재 정점에서 한 방향으로 길이 막힐때까지 깊게 파고드는 방법으로,

막힌 부분을 만났을 땐 마지막에 따라온 간선으로 되돌아간다.

후입선출

 

---

 BFS, Breadth First Search (너비 우선 탐색) - queue

> 가까운 정점을 먼저 방문하고 먼 정점은 나중에 방문한다.

선입선출

 

---

''.join([chr(i) for i in [66,69,65,84])
#'BEAT'