크래프톤 정글 week02, day17 - 알고리즘 문제

위상정렬 알고리즘

• 줄 세우기 문제를 풀기 위해 학습했던 알고리즘

from collections import deque

# 위상정렬 알고리즘(꼭짓점, 간선정보 매개체)
def topological_sort(vertices, edges):
    # 각 꼭짓점에서 다른 꼭짓점으로의 간선정보를 저장할 인접리스트 만들기
    # 함수를 사용할 때마다 새롭게 작성해야하므로 함수 내부에 작성
    # 0은 무시하고 1부터시작해야하기 때문에 +1로 맞춤
    adj = [[] for _ in range(vertices + 1)]
    # 꼭짓점으로 들어오는 간선의 수를 저장할 리스트
    # 0은 무시하고 1부터시작해야하기 때문에 +1로 맞춤
    indegree = [0] * (vertices + 1)
    
    # 간선 정보를 돌리면서
    for edge in edges:
        # 시작노드, 끝노드를 저장
        start, end = edge
        # 시작노드리스트에 끝노드를 추가
        adj[start].append(end)
        # 끝 노드에 연결되었으므로 끝노드 값에 + 1
        indegree[end] += 1

    # 결과값 리스트 생성 및 데크 선언
    result = []
    q = deque()

    # 꼭짓점 개수만큼 돌려서(1부터 시작하기 때문에 +1)
    for i in range(1, vertices + 1):
        # 만약 연결되는 간선 수가 0이면
        if indegree[i] == 0:
            # 큐에 추가
            q.append(i)

    # 큐가 없어질 때까지 반복
    while q:
        # 큐에서 pop한 노드를 now에 저장
        now = q.popleft()
        # result 리스트에 추가
        result.append(now)
        # 간선정보리스트를 돌려서
        for i in adj[now]:
            # 현재 노드는 이미 처리되었으니 노드로 들어오는 간선 제거
            indegree[i] -= 1
            # 만약 현재 노드긔 간선이 0이라면
            if indegree[i] == 0:
                # 큐에 추가
                q.append(i)

    return result
# 꼭짓점 개수
vertices = 7
# 간선 정보
edges = [(1, 2), (1, 5), (2, 3), (2, 6), (3, 4), (4, 7), (5, 6), (6, 4)]
print(topological_sort(vertices, edges))

 

줄 세우기

• n 명의 학생을 키를 비교하여 줄 세우기

from collections import deque
import sys

# 줄세우기 함수
def student_line(n, edges):
    # 연결된 학생들 체크하는 line
    line = [[] for _ in range(n+1)]
    # 우선순위가 몇 차인지 확인하는 count
    count = [0] * (n+1)

    # edges를 돌려서 시작학생, 끝학생을 a, b에 담고
    for edge in edges:
        a, b = edge
        # b학생에게 a학생을 입력(거꾸로 한 방식)
        line[b].append(a)
        # a학생의 우선순위 1 증가
        count[a] += 1

    # 줄 세우는 결과값 생성
    result = []
    # 데크 선언
    queue = deque()

    # 학생 수 만큼 반복하면서(학생 수는 1부터 시작하므로 n+1)
    for i in range(1, n+1):
        # 만약 우선순위가 0인 학생이 있으면 큐에 삽입
        if count[i] == 0:
            queue.append(i)

    # 큐가 없어질때까지 반복하며
    while queue:
        # 현재 학생 now에 큐에 가장 먼저 넣은 값을 넣고 result리스트에 넣기
        now = queue.popleft()
        result.append(now)

        # 현재 학생의 연결된 학생을 돌려서 우선순위를 1 낮춘다
        for i in line[now]:
            count[i] -= 1

            # 만약 낮췄을 때 그 학생의 우선순위가 0이면 큐에 삽입
            if count[i] == 0:
                queue.append(i)
    # 결과값 반환
    return result

# 학생 수 n, 학생끼리 비교 수 m, 누구랑 비교했는지 edges
n, m = list(map(int, sys.stdin.readline().split()))
edges = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

# 줄세우기 함수를 실행한 리턴값을 변수에 저장
jjin_result = student_line(n, edges)
# 변수의 배열을 리버스 시켜서 출력
jjin_result.reverse()
# 출력시 *을 붙이면 [] 같은 배열이나 , 같은 특수기호를 생략하고 값만 뽑아낸다
print(*jjin_result)

위상정렬을 이용한 문제이며, 첫 주차 팀원에게 컵라면 먹는 데까지의 준비과정을 비유로 들으며 위상정렬의 개념을 깔끔하게 이해했다.

알고리즘 코드를 보고 잘 대입해서 풀면 풀 수 있는 문제

​

트리의 부모 찾기

• 노드의 개수 n개만큼 받고 n-1개의 간선 수를 입력받아 각 노드의 부모 노드 찾기

# 노드 개수 n, 둘째 줄부터 n-1개의 줄에 트리상에서 연결된 두 정점을 입력받음
# 루트 노드가 1번이라고 가정할 때, 1번을 제외한 노드를 2번부터 순서대로 자기의 부모 노드를 출력

# --------------재귀로 구현----------------------
# import sys
# sys.setrecursionlimit(10000)

# def dfs(v, edges, visited, mom):
#     visited[v] = True

#     for i in edges[v]:
#         if not visited[i]:
#             mom[i] = v
#             dfs(i, edges, visited, mom)

# # n = int(sys.stdin.readline())
# n = int(input())
# edges = [[] for _ in range(n+1)]

# for _ in range(n-1):
#     # a, b = map(int, sys.stdin.readline().split())
#     a, b = map(int, input().split())
#     edges[a].append(b)
#     edges[b].append(a)

# visited = [False] * (n+1)

# mom = [0] * (n+1) 

# dfs(1, edges, visited, mom)

# for i in range(2, n+1):
#     print(mom[i])

# ------------스택으로 구현(재귀 런타임에러로 실패)-------------------

# 노드 개수 n, 간선정보 edges, 방문확인 visited, 부모노드확인 mom 
n = int(input())
edges = [[] for _ in range(n+1)]

for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

visited = [False] * (n+1)
mom = [0] * (n+1)
# 루트노드가 1로 고정인 상태이기 때문에 1로 시작
stack = [1]

# 스택이 없을 때까지 반복
while stack:
    # 스택을 pop해서 v에 넣기
    v = stack.pop()
    # 만약 v가 방문하지 않았다면 v를 방문체크
    if not visited[v]:
        visited[v] = True
        # v의 연결점을 확인해서 방문안한 노드가 있으면 
        for i in edges[v]:
            if not visited[i]:
                # 현재 노드를 i의 부모로 저장하고 자식노드를 스택에 추가
                mom[i] = v
                stack.append(i)

# 1은 루트노드이기 때문에 패스하고 2부터 n+1까지 mom출력
for i in range(2, n+1):
    print(mom[i])

깔끔하게 재귀로 구현했으나 재귀오류로 인해 스택으로 해결. 여전히 스택은 잘 못해서 지피티의 힘을 빌렸다..

​

이분그래프

• 그래프가 입력으로 주어졌을 때 연결되는 노드의 색깔이 다른지 체크해서 맞으면 YES 틀리면 NO를 반환

# 1번 줄 테스트 케이스 개수 k
# 2번 줄 정점v, 간선개수e 입력
# 3번 줄 부터 간선을 이루는 두 정점 u, v 입력
import sys
# 재귀함수 최대 10000번
sys.setrecursionlimit(10**4)

# 테스트 케이스 k
k = int(sys.stdin.readline())

# 깊이 탐색 함수
def dfs(graph, v, visited, color):
    visited[v] = True

    for i in graph[v]:
        if visited[i]:
            if color[i] == color[v]:
                return False
        else:
            color[i] = not color[v]
            if not dfs(graph, i, visited, color):
                return False
    return True

# 이분 그래프 함수
def binary_graph(k):
    # k만큼 반복 : 정점v, 간선개수 e, 방문확인 visited, 간선정보 graph, 색깔비교 color
    for _ in range(k):
        v, e = list(map(int, sys.stdin.readline().split()))
        visited = [False] * (v+1)
        graph = [[] for _ in range(v+1)]
        color = [False] * (v+1)

        # 간선 갯수만큼 반복하여 a, b에 시작노드, 끝노드 넣고 각 연결노드 확인에 삽입
        for _ in range(e):
            a, b = list(map(int, sys.stdin.readline().split()))
            graph[a].append(b)
            graph[b].append(a)

        # 그래프를 확인하고 Yes를 출력할지 No를 출력할지 체크하는 변수
        YesNo = True
        # 1부터 정점+1까지 방문안한 노드가 있으면:
        for i in range(1, v+1):
            if not visited[i]:
                # 만약 dfs의 return값이 false라면 YesNo를 false로 바꾸고 빠져나오기
                if not dfs(graph, i, visited, color):
                    YesNo = False
                    break

        # 체크 변수에 따라 yes혹은 No 출력
        print("YES" if YesNo else "NO")

binary_graph(k)

열심히 공부한 dfs로 스스로 거의다 작성했는데 색깔을 False, True로 정해논 값을 체크해서 출력시키는 것에 한계가 와서 지피티 선생님이 보충해주셨다. 지피티 없인 못살아

​

학습시간 : 10 ~ 24시