Willing

1. 위상 정렬이란?

위상 정렬 (Topology Sort)

• 순서가 정해져 있는 작업 을 차례로 수행해야할 때, 그 순서를 결정해주는 알고리즘
• 순차적으로 어떤 그래프가 형성되어 있을 때, 해당 그래프를 하나의 경로로 표현
• 여러 나열 방법이 있을 수 있기 때문에 답이 다양하게 나올 수 있음
• DAG에만 적용 가능
  • DAG : Directed Acyclic Graph, 사이클이 존재하지 않는 방향 그래프
  • 위상 정렬은 시작점이 존재해야 하지만, 사이클 그래프에서는 시작점을 찾을 수가 없음

위상 정렬에서 알 수 있는 두 가지

• 현재 그래프가 위상 정렬이 가능한가?
• 위상 정렬이 가능하다면 그 결과는 무엇인가?

2. 위상 정렬 구현

큐를 이용한 방식

1. 진입차수가 0인 정점을 큐에 삽입
   • 진입차수가 0인 정점이 여러 개 존재할 경우 어느 정점이든 무방
   • 초기에 간선의 수가 0인 모든 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거
   • 선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소
3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입
4. 큐가 빌 때까지 2번 ~ 3번 과정 반복
   • 모든 원소를 방문하기 전에 큐가 빈다면 => 사이클 존재
   • 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과

스택을 이용한 방식

1. 그래프에서 방문하지 않은 노드면 DFS를 수행
2. DFS가 끝나면 해당 노드를 스택에 추가
3. 스택에서 하나씩 꺼내면 위상 정렬된 노드들을 얻을 수 있음 (역순으로 출력하는 것과 같은 결과)

3. 코드 구현

큐를 이용한 방식

import queue

# 그래프의 인접 행렬
graph = {0: [1, 2, 3], 1: [4], 2: [4, 5], 3: [], 4:[6], 5:[1], 6: []}

def topology_sort_queue(graph):
    N = len(graph)
    sort_queue = queue.Queue() # 큐
    degree = [0 for _ in range(N)] # 진입차수 리스트

    for nodes in graph:
        for j in graph[nodes]:
            degree[j] += 1
    print("진입차수 리스트 : ", degree)

    for i in range(N):
        if degree[i] == 0: sort_queue.put(i)

    answer = []
    while not sort_queue.empty():
        current = sort_queue.get()
        answer.append(current)
        for i in graph[current]:
            degree[i] -= 1
            if degree[i] == 0 : sort_queue.put(i)
    print("최종 답 : ", answer)

topology_sort_queue(graph)

스택을 이용한 방식

# 그래프의 인접 행렬
graph = {0: [1, 2, 3], 1: [4], 2: [4, 5], 3: [], 4:[6], 5:[1], 6: []}

def topology_sort_stack(graph):
    N = len(graph)
    stack = [] # 스택
    visited = [0 for _ in range(N)] # 방문확인 리스트

    for i in graph:
        if visited[i] == 0:
            dfs(i, stack, visited)
    
    answer = []
    while len(stack) != 0:
        answer.append(stack.pop())
    print("최종 답 : ", answer)

def dfs(v, stack, visited):
    visited[v] = 1
    for i in graph[v]:
        if visited[i] == 0: dfs(i, stack, visited)
    stack.append(v)
topology_sort_stack(graph)

#. References

• velog.io/@max9106/Algorithm-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%ACTopology-Sort
• m.blog.naver.com/ndb796/221236874984
• haedallog.tistory.com/122

1. input

* 입력받아야하는 값의 개수가 엄청나게 많을 때는 시간 초과를 유발할 수 있음!!

x = input()

- 사용자에게 값을 입력받아 변수에 저장

- 모든 입력값을 문자열(string)으로 취급

x = int(input())

- 형변환을 통해 원하는 자료형으로 변환 가능

x, y = map(int, input().split())

- 위와 같은 방식으로 원하는 자료형의 데이터를 여러 개 입력 받을 수 있음

2. sys.stdin

import sys
for line in sys.stdin:
	print(line)

- 여러 줄 입력받음

3. sys.stdin.readline

import sys
N = input()
a = [sys.stdin.readline() for _ in range(N)]

- 한 줄 입력받을 때 사용

- 위와 같은 방식으로 여러 줄 입력받을 수 있음

! 입출력 속도

sys.stdin.readline > raw_input() > input()

● 2020 KAKAO BLIND RECRUITMENT 문제

● 출처 : 프로그래머스 코딩 테스트 연습, programmers.co.kr/learn/courses/30/lessons/60058

● 코드 - Python

def check(u):
    if u[0] == ")": return 0

    cnt = 0
    for i in range(len(u)):
        if cnt < 0 : return 0
        elif u[i] == "(": cnt += 1
        else: cnt -= 1
    return cnt == 0

def reverse(u):
    reversed = ""
    for i in range(len(u)):
        if u[i] == ")": reversed += "("
        else: reversed += ")"
    return reversed

def devide(v):
    u, cnt = "", 0
    if v == "": return v

    for i in range(len(v) + 1):
        if cnt == 0 and i > 0 : 
            if check(u):
                return u + devide(v[i:])
            else:
                u = u[1:-1]
                return "(" + devide(v[i:]) + ")" + reverse(u)
        elif v[i] == "(": 
            u += v[i]
            cnt += 1
        else: 
            u += v[i]
            cnt -= 1


def solution(p):
    if check(p):
        return p
    else :
        return devide(p)

- check : 문자열이 올바른 문자열인지 아닌지를 검사하는 함수. 올바른 문자열이라면 1을, 그렇지 않다면 0을 반환

- reverse : 괄호를 뒤바꾸는 함수. ) -> ( 로, ( -> ) 로 바꿔줌

- devide : 문자열을 u 부분과 v 부분으로 나누어 재귀를 도릴 수 있게 하는 함수. )와 (의 개수가 같은지를 cnt를 통해 확인하여 u, v로 분리한 후 check를 통해 해당 u가 올바른 문자열인지 아닌지를 판단하여 그에 맞게 처리

! BLOCKING POINT

1. v가 빈 문자열인 경우

• 처음 devide안의 for문에서 범위 설정을 len(v)까지로만 해주었었는데, 그 경우 for문을 다 돌고 끝날때 예외처리를 해주지 못했다.
• 즉 v가 "()"의 형태일 때 마지막 괄호를 넣음으로써 비로소 cnt가 0이 되는데, for문 밖으로 나와버리므로 안의 분기로 들어가지 못했던 것
• for문의 범위를 len(v) + 1로 함으로써 마지막 원소까지 넣은 후 한 번 더 돌 수 있게 해준 후, v = ""일 경우의 예외 분기를 추가해주었다.
• 아직 맘에 들지 않는 부분 -> 다른 방법으로 처리할 수 있는지 알아볼 것

2. "괄호를 뒤집는다"의 잘못된 이해

• 처음에는 단순히 순서를 뒤집는다는 뜻으로 이해
• u[::-1]  구문을 통해 reversed() 방식을 수행 -> 12번 부터 오답 판정
• 질문 게시판을 찾아보니 순서를 뒤집는 것이 아닌 괄호의 방향자체를 바꾸는 것이었음
• reverse라는 함수를 새로 추가해주며 해당 문제 해결