스택(stack), DFS(깊이 우선 탐색), 이분 그래프, 백준 1707 파이썬

1. 스택

삽입과 삭제가 LIFO(후입선출) 방식으로 이루어진 자료구조

구현 방법

0번 강의에서 언급했듯이 파이썬에선 리스트로 간단하게 스택 구현이 가능

 

리스트 이름이 s일때

• s.appped(data): top 위치에 새로운 데이터를 삽입하는 연산
• s.pop(): top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• s[-1]: top 위치에 현재 있는 데이터를 단순 확인하는 연산

쓰이는 곳

• DFS
• 쌍이 맞아야 하는 문제(괄호 여닫기 등)

2. DFS

그래프: 노드(정점)와 에지(간선)로 이루어진 자료구조

 

그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후, 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 그래프 완전 탐색 알고리즘

 

시간 복잡도(노드 수: V, 에지 수: E): O(V + E)

 

시간 복잡도가 중요한 이유:

시간 복잡도는 문제를 풀 때 알고리즘 선택의 기준이 되기 때문입니다.

어려운 알고리즘 문제는 문제를 보아도 어떤 알고리즘, 자료구조를 써야 하는지 모르는 경우가 대다수입니다. 이럴 때 각 알고리즘의 시간 복잡도를 알고 있다면 주어지는 입력값과 비교하여 가능한 알고리즘을 추릴 수 있습니다.

가지고 있는 도구(알고리즘 및 자료구조 등) 중에 어떤 도구를 선택해야 하는지 후보를 추릴 수 있다면 문제해결방법을 고민하는 과정이 크게 단축됩니다. 

대략적인 기준으로는 입력값 10^8 기준으로 1초가 걸린다고 생각해주시면 될 것 같습니다.

즉, 1초든 2초든 작은 상수의 영향이 미미한 프로그래밍 세계에서는 10^8안의 연산값으로 해결해야 한다고 생각해주시면 됩니다.

 

시간 복잡도에 대한 자세한 내용은 빅오-표기법에 대해서 검색하여 공부하셔야 합니다.

구현 방법

DFS를 구현하려면 아래 두 가지 핵심 지식(인접 리스트, 재귀 함수)을 알아야 함

 

파이썬에서 그래프는 일반적으로 인접 리스트 형태로 표현

 

인접 리스트:

1. 리스트의 각 index를 노드라 생각하고, 리스트내 원소를 에지라 생각하는 구조. (노드가 1번부터 시작하는 경우가 많기 때문에 index 0은 비워줌)

EX) 1, 2, 3의 노드가 존재하고 에지는 1 -> 2, 2 -> 3, 1-> 3이 존재한다고 하면 리스트의 형태는 [[], [2, 3], [3], []].

 

2. 한 번 방문한 노드를 다시 방문하면 안되므로 노드 번호를 index로 하는 방문 여부를 체크할 리스트가 필요 visited_list = [False, False, False, False]

 

재귀 함수:

파이썬에서 함수를 호출하고 나면 그 함수가 종료 된 뒤 기존 함수가 진행

EX)f 함수에서 f2를 호출하면 f2가 종료된 뒤 f의 나머지 코드들이 실행

 

위 두개 개념을 이용하여 구현

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
   1. 원본 그래프를 인접 리스트로 그래프 표현하기
   2. 방문 리스트 초기화하기
   3. 시작 노드를 스택에 삽입(재귀 함수로 표현하면 자동 해결)하기
2. DFS 함수 제작
   1. 인수로 현재 node값을 가지는 DFS 함수를 제작
   2. 함수는 현재 node에서 갈 수 있는 node들에 대해, 방문하지 않았다면 방문 처리 + DFS 함수 호출을 진행
   3. 문제 상황에 맞게 함수 내에 기능을 추가
3. 시작 노드에서 생성된 DFS 함수를 호출

3. 이분 그래프

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프

예시)

1 -> 2-> 3은 1번 노드 1집합, 2번노드 2집합, 3번 노드 1집합을 하면 되므로 가능.

1 -> 2-> 3->1은 1번 노드 1집합, 2번노드 2집합, 3번 노드 1집합을 하면 1번과 3번이 이웃함에도 1번 집합이라 불가능

 

4. 문제

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

Basic Idea:

방문 여부를 체크하는 방문 리스트를 각 집합의 이름으로 설정하여 함수를 구성

 

구현 방법

1. 이웃한 노드들을 집합으로 구분(방문하여 어떤 집합에 속하는지 처리)해야 하므로 탐색 알고리즘 사용

입력 값:

• 2 ≤ K ≤ 5
• 1 ≤ V ≤ 20,000
• 1 ≤ E ≤ 200,000

시간 복잡도: 탐색 알고리즘 DFS의 경우 O(V + E)이므로 테스트 케이스 개수까지 고려할 시 약 10^6 연산이 필요하므로 구현 가능

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)	# 함수 내 함수 호출을 10^6까지 일시적으로 허용
T = int(input())

n_list = []						# 노드 인접 리스트
v_list = []						# 몇번 그룹을 방문 했는지 리스트
is_possible = True
def dfs(cur_node, group_num):	# 이분 그래프라 그룹이 2개인지 확인해야 하므로 인수를 추가
    global is_possible
    for new_node in n_list[cur_node]:
        if not is_possible:
            break
        if v_list[new_node] == 0:		# 방문하지 않았다면
            if group_num == 1:			# 현재 그룹이 1번이라면
                v_list[new_node] = 2	# 
            else:
                v_list[new_node] = 1
            dfs(new_node, v_list[new_node])
        elif v_list[new_node] == 1:
            if group_num == 1:
                is_possible = False
                break
        else:
            if group_num == 2:
                is_possible = False
                break



for t_cnt in range(T):
    V, E = map(int, input().split())
    n_list = [[] for i in range(V + 1)]
    v_list = [0] * (V + 1)
    is_possible = True
    for i in range(E):
        node1, node2 = map(int, input().split())
        n_list[node1].append(node2)
        n_list[node2].append(node1)

    for i in range(1, V+1):
        if v_list[i] == 0:
            dfs(i, 1)
            if not is_possible:
                is_possible = True
                dfs(i, 2)
                if not is_possible:
                    break

    if is_possible:
        print('YES')
    else:
        print('NO')