[2024.02.08] Stack 1

DP (Dynamic Programming) ; 동적 계획

: 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다. 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘이다.

DFS (깊이우선탐색)

• 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요함

• 깊이 우선 탐색(DFS) / 너비 우선 탐색(BFS)

• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법

• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용

'''
7 8
1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7
'''
def dfs(i, V): #시작 i, 마지막 V
    visited  = [0] * (V+1) #visited, stack 생성 및 초기화
    st = []
    visited[i] = 1 #시작점 방문
    print(i) #정점에서 할 일
    while True: #탐색
        #현재 방문한 정점에 인접하고 방문 안 한 정점 w가 있으면,
        for w in adjl[i]:
            if visited[w] == 0:
                st.append(i) #push(i), i를 지나서
                i = w #w에 방문
                visited[i] = 1 #방문해서 할 일
                print(i)
                break #for w, 
        else: #for w, i에 남은 인접 정점이 없으면,
            if st: #스택이 비어있지 않으면(지나온 정점이 남아 있으면),
                i = st.pop()
            else: #스택이 비어있으면(출발점에서 남은 정점이 없으면),
                break #while True
    return
            
V, E = map(int, input().split())
arr = list(map(int, input().split()))

#인접리스트
adjl = [[] for _ in range(V+1)]
for i in range(E):
    n1, n2 = arr[i*2], arr[i*2+1]
    adjl[n1].append(n2)
    adjl[n2].append(n1) #방향이 없는 경우
dfs(1, V)

'''
7 8
1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7
'''

def dfs(i): #시작 i, 마지막 V
    visited[i] = 1 #방문 표시
    print(i) #출력
    #i에 인접하고 방문 안 한 w가 있으면,
    for w in adjl[i]:
        if visited[w] == 0:
            dfs(w)
            
V, E = map(int, input().split())
arr = list(map(int, input().split()))

#인접리스트
adjl = [[] for _ in range(V+1)]
for i in range(E):
    n1, n2 = arr[i*2], arr[i*2+1]
    adjl[n1].append(n2)
    adjl[n2].append(n1) #방향이 없는 경우
visited = [0] * (V+1) #visited, stack 생성 및 초기화
dfs(1)

# - 그래프: 데이터들끼리 다대다 관계를 가지게 되는 자료구조
#    N : M 표현 -> 1. 인접 행렬 (2차원 배열) / 2. 인접 리스트 (해당 정점 i에 대해서 연결이 되어있는(인접한) 정점의 정보를 담는 리스트)
#    메모리 문제 발생할 수 있음.

# - 인접 리스트 : 정점 i가 인접한 (연결 관계를 가진) 노드 정보를 리스트로 저장
#    정점의 개수 v와 간선의 개수 E (해당 노드들 사이 다리의 개수)   
V, E = map(int, input().split()) # 5, 8
adj = [[] for _ in range(V+1)] # 노드 개수 N만큼 비어있는 리스트를 준비

# 반복문을 통해서 간선의 정보를 각각 입력받는다.
# 각 줄에 시작점과 종료점을 입력
for _ in range(E): #간선의 개수만큼 순회
    # 해당 줄에 시작점 종료점 정보를 입력
    start, end = map(int, input().split()) # '1 2' 1 <-> 2
    # 시작 정점과 끝 정점을 서로 연결한다.
    adj[start].append(end) # [[], [2], ...]
    adj[end].append(start) # 양방향으로 start <-> end 정점을 서로 연결
    
# DFS 탐색 ... 시작 정점 i가 주어진다면? (재귀함수)
def dfs(i):
    # 현재 노드를 방문체크! (출력)
    visited[i] = True
    print('-', i, end='')
    
    # 현재 노드로부터 인접한 노드를 계속해서 방문! (탐색)
    for w in adj[i]: # 인접한 노드들을 순회
        # 아직 방문하지 않았던 노드만 방문
        if visited[w]:
            dfs(w)
    

# 방문 체크를 하기 위한 visited 배열
visited = [False] * (V+1)
dfs(1) #1번 정점을 시작으로 해서 나머지 정점들을 모두 탬색