Coding 공부

import sys
input = sys.stdin.readline
N,M = map(int,input().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    graph[y].append(x)


start = int(input())
stack = [start]
cnt = 0
visited = [True for _ in range(N+1)]
visited[start] = False
while stack:
    x = stack.pop()

    for next_node in graph[x]:
        if visited[next_node]:
            visited[next_node] = False
            cnt += 1
            stack.append(next_node)

print(cnt)

주어진 작업을 시행하기위해서 필요한 작업의 양을 구하는 방법은

처음에 들어온 입력을 자식노드에 부모노드를 기억해놓고,

주어진 노드에서부터, 부모로 가면서 부모의 수를 세어주면 된다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)
def root_dfs(node):
    if visited[node]:
        return
    visited[node] = True
    child_list = []
    for next_node in tree[node]:
        if not visited[next_node]:
            child_list.append(next_node)

    if len(child_list)==2:
        return [node,0]
    elif len(child_list) == 1:
        return_value = root_dfs(child_list[0])
        return_value[1] += tree[node][child_list[0]]
        return return_value
    else:
        return [node,0]

def leef_dfs(node):
    if visited[node]:
        return
    visited[node] = True
    child_list = []
    for next_node in tree[node]:
        if not visited[next_node]:
            child_list.append(next_node)
    
    if len(child_list)==0:
        return 0
    else:
        result = 0
        for child_node in child_list:
            result = max(result,leef_dfs(child_node)+tree[node][child_node])
        return result
N,R = map(int,input().split())
tree = [{} for _ in range(N+1)]
for _ in range(N-1):
    x,y,b = map(int,input().split())
    tree[x][y] = b
    tree[y][x] = b


visited = [False for _ in range(N+1)]

root_node_info = root_dfs(R)
visited[root_node_info[0]] = False
leef_dis = leef_dfs(root_node_info[0])
print(root_node_info[1],leef_dis)

2개의 DFS로 나눠서 최초엔 풀었다.

첫번째 풀이는 두개로 나뉘어서 DFS를 했다.

첫 DFS는 기가노드를 찾는것이다. 기가노드를 찾으면 그때의 길이를 저장해놓는다.

그리고 기가노드에서 부터 리프노드까지 최대 길이를 찾아내는 방식으로 해서 구했다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(300000)
def root_dfs(node,dis):
    if visited[node]:
        return
    visited[node] = True
    count = 0
    nexts = -1
    distance = 0
    for next_node in tree[node]:
        if not visited[next_node]:
            count += 1
            nexts = next_node
            distance += tree[node][next_node]
    if count == 1:
        return root_dfs(nexts,dis+distance)
    else:
        return [node,dis]

def leaf_dfs(node,dis):
    global leef_dis
    visited[node] = True
    count = 0
    for next_node in tree[node]:
        if not visited[next_node]:
            leaf_dfs(next_node,dis+tree[node][next_node])
            count += 1
    if not count:
        leef_dis = max(leef_dis,dis)


N,R = map(int,input().split())
tree = [{} for _ in range(N+1)]
for _ in range(N-1):
    x,y,b = map(int,input().split())
    tree[x][y] = b
    tree[y][x] = b


visited = [False for _ in range(N+1)]
root_dis = root_dfs(R,0)
leef_dis = 0
leaf_dfs(root_dis[0],0)
print(root_dis[1],leef_dis)

두번째 풀이는 좀더 깔끔한 풀이이다.

count를 별도로 세주어서 기가노드인지 리프노드인지 구분을 해주었다.

기가노드가 아닐때에는 재귀를 해주면서 distance를 더해주고, 만약 기가노드일때는 재귀를 머추고, 기가노드의 위치와

지금까지 누적된 거리를 반환해준다.

leaf_dfs도 비슷한 과정을 겪는다.

leaf_dfs를 계속 재귀를 통해 가면서 leaf_node에 도착하면 현재까지 누적된 값과 최대값과 비교를 해서 더 큰 값을 넣어주면 된다.

import sys
import heapq
input = sys.stdin.readline


N,M,T = map(int,input().split())



graph = [{} for _ in range(N+1)]
INF = float('inf')
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,INF),pay)
    graph[y][x] = min(graph[y].get(x,INF),pay)


conquer = -1
pay_list = [[INF for _ in range(N+1)] for _ in range(2)]
pay_list[0][1] = 0
visted = [False]*(N+1)
cur_pay,cur_node = 0,1
result = 0
total_city = set(range(1,N+1))
while conquer<N-1:
    if visted[cur_node]:
        continue
    visted[cur_node] = True
    result += cur_pay
    total_city.remove(cur_node)
    conquer += 1
    idx = conquer%2
    if conquer > 0:
        prev_idx = (conquer+1)%2
        for city_num in total_city:
            pay_list[idx][city_num] = pay_list[prev_idx][city_num]+T
    
    min_idx = -1
    min_pay = INF
    for next_node in graph[cur_node]:
        temp_pay = graph[cur_node][next_node] + conquer*T
        if pay_list[idx][next_node] > temp_pay:
            pay_list[idx][next_node] = temp_pay

    for city_num in total_city:
        if min_pay > pay_list[idx][city_num]:
            min_pay = pay_list[idx][city_num]
            min_idx = city_num
    cur_pay,cur_node = min_pay,min_idx


print(result)

 이 문제는 어렵게 생각해서 오래 걸렸던 문제였다. 이 문제를 쉽게 생각해보면, conquer 비용은 고정적이다.

이 conquer 비용을 생각지 않고, 가장 마지막까지 구하고 난뒤에 conquer 비용만 더해주면 되는 문제이긴했다.

하지만 풀때에는 이 방식에 대해 잘 몰랐고, 그걸 적용시키지 않고, conquer 비용을 바로바로 구해주었다.

이 풀이의 방식은 다음과 같다 pay_list를 2*(N+1)로 해주었다.

즉 우리가 프림알고리즘에서 pay를 저장하는걸 1차원 배열 하나로 했던 거에 비해 2차원 배열을 이용해서 문제를 풀었다.

각각의 의미는 다음과 같다. 현재의 conquer 수치를 같이 저장을 해주면서

현재 conquer가 짝수이면, 0이고, 그때의 이전 pay_list 비용은 1번 인덱스에 있다.

현재 conquer가 홀수이면 1이고, 그때의 이전 pay_list 비용은 0번 인덱스에 있다.

즉 슬라이딩 윈도우처럼 각 전단계의 pay_list를 가져와서 현재 우리가 구하고자 하는

pay_list에 덮어씌워주는 방식으로 했다.

그 뒤에는 일반적인 프림알고리즘과 비슷하다.

현재 노드에서 갱신될수 있는것들을 전부 갱신을 한뒤에

모든 도시들을 찾아다니면서 가장 작은 값을 구해주면 되는 것이다.

import sys
import heapq
input = sys.stdin.readline


N,M,T = map(int,input().split())



graph = [{} for _ in range(N+1)]
INF = float('inf')
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,INF),pay)
    graph[y][x] = min(graph[y].get(x,INF),pay)



pay_list =[INF for _ in range(N+1)]
node_list = []
visited = [False]*(N+1)
heapq.heappush(node_list,(0,1))
pay_list[1] = 0
result = 0
while node_list:
    cur_pay,cur_node = heapq.heappop(node_list)
    if pay_list[cur_node] < cur_pay or visited[cur_node]:
        continue
    visited[cur_node] = True
    result += cur_pay
    for next_node in graph[cur_node]:
        if pay_list[next_node] > graph[cur_node][next_node] and not visited[next_node]:
            pay_list[next_node] = graph[cur_node][next_node]
            heapq.heappush(node_list,(pay_list[next_node],next_node))


conquer_pay = (N-2)*(T+(N-2)*T)//2
result += conquer_pay
print(result)

이 풀이는 위에서 말한것처럼 어차피 conquer는 등차수열로 균등하게 증가하기 때문에, conquer를 배제하고,

우리가 일반적으로 구하는 프림알고리즘을 이용해서 문제를 해결한다.

그리고 난뒤에 등차수열의 합의 공식을 이용해서, conquer_pay를 구한뒤 결과값에 더해주면 된다.

from collections import deque

N = int(input())
if N == 1:
    print(0)
    print(1)
else:
    dp_dict = {N:-1}
    stack = [N]
    cnt = 0
    while stack:
        new_stack = []
        for num in stack:
            if not (num%3 or dp_dict.get(num//3)):
                dp_dict[num//3] = num
                new_stack.append(num//3)
            if not (num%2 or dp_dict.get(num//2)):
                dp_dict[num//2] = num
                new_stack.append(num//2)
            
            if not dp_dict.get(num-1) and num>1:
                dp_dict[num-1] = num
                new_stack.append(num-1)
        cnt += 1
        if 1 in new_stack:
            break
        stack = new_stack[:]
    result = []

    find_num = 1
    print(cnt)
    while True:
        result.append(find_num)
        find_num = dp_dict[find_num]
        if find_num == -1:
            break
    result.reverse()
    print(*result)

방식은 간단하다. 나눠지고, 해당 값이 최초로 방문했을때에만 new_stack에 넣어주고,

그때의 위치정보를 dictionary에 저장시켜준다.

그리고 1에 도착하면 역으로 추적해가면서 최초의 숫자가 나올때까지 반복을 해주면 되는 문제이다.

import sys
from collections import deque,defaultdict
input = sys.stdin.readline
# 강의 근원 노드의 순서는 1이다.

T = int(input())

for _ in range(T):
    K,M,P = map(int,input().split())
    # K case의 번호
    # M은 노드의 수
    # P는 간선의 수

    strahelr_dict = [defaultdict(int) for _ in range(M+1)]
    strahelr_list = [-1 for _ in range(M+1)]
    graph = [[] for _ in range(M+1)]
    indegree_list = [0 for _ in range(M+1)]
    for _ in range(P):
        x,y = map(int,input().split())
        graph[x].append(y)
        indegree_list[y] += 1
    stack = deque()
    for i in range(1,M+1):
        if not indegree_list[i]:
            stack.append(i)
            strahelr_list[i] = 1
    
    while stack:

        node = stack.popleft()
        cur_strahler = strahelr_list[node]
        for next_node in graph[node]:
            indegree_list[next_node] -= 1
            strahelr_dict[next_node][cur_strahler] += 1
            if not indegree_list[next_node]:
                stack.append(next_node)
                next_strahelr = max(strahelr_dict[next_node].keys())
                if strahelr_dict[next_node][next_strahelr] > 1:
                    strahelr_list[next_node] = next_strahelr + 1
                else:
                    strahelr_list[next_node] = next_strahelr



    print(K,strahelr_list[M])

 이 문제에서 주의해야할 점은,  마지막에 출력해야할 TEST CASE의 값이 T가 아니라, K인걸 주의해야한다.

처음은 위상정렬을 해주는 것과 동일하게 indegree와 graph를 그려준다.

가장 처음에 출발하는 node들의 strahler의 값을 1로 초기화를 해준다.

위상정렬을 해주면서, 방문하는 노드들에 해당 cur_strahler의 개수를 세줍니다.

그러면서 indegree가 0이 되었을때, 최대값을 찾고, 그 개수가 2개 이상이면, 최대값보다 1을 더해서 저장시켜줬습니다.

위와 같이 한뒤에 나머지는 일반적인 위상정렬을 구하면 되는 문제였습니다.

# 42_jakang님 풀이
import sys
input = sys.stdin.readline


def tree_dp(cur_node):

    if not len(graph[cur_node]):
        strahler_list[cur_node] = 1
        return
    else:
        max_st_cnt = 0
        for parent_node in graph[cur_node]:
            tree_dp(parent_node)

            if strahler_list[cur_node] < strahler_list[parent_node]:
                strahler_list[cur_node] = strahler_list[parent_node]
                max_st_cnt = 1
            elif strahler_list[cur_node] == strahler_list[parent_node]:
                max_st_cnt += 1
        if max_st_cnt > 1:
            strahler_list[cur_node] += 1
T = int(input())

for _ in range(T):
    K,M,P = map(int,input().split())
    strahler_list = [0 for _ in range(M+1)]
    graph = [[] for _ in range(M+1)]

    for _ in range(P):
        x,y = map(int,input().split())
        graph[y].append(x)

    

    tree_dp(M)
    print(K,strahler_list[M])
    

 이 풀이는 42_jakang님의 풀이를 공부하면서 한것이었고, 이 풀이 방식은 다음과 같습니다.

어차피 가장 끝노드 M은 고정되어있으므로, 가장 끝 노드에서부터 하나하나씩 부모를 찾아 들어가봅니다.

그리고 부모노드의 strahler_list가 현재노드보다 크면 갱신을 해주고, 그 큰값들의 개수를 세줍니다.

만약에 그 개수가 2개 이상이면, 현재노드의 shrahler의 값을 키워줍니다.

이런 방식을 이용해서도 문제를 풀 수 있습니다.

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())


for tc in range(T):
    N = int(input())
    graph = [[0 for _ in range(N+1)] for _ in range(N+1)]
    # 전년도 1등부터 ~ N등까지 팀 순서
    prev_order_team = list(map(int,input().split()))
    indegree = [0]*(N+1)
    indegree[0] = float('inf')
    for rank,team_num in enumerate(prev_order_team):
        indegree[team_num] = rank
        for low_team_num in prev_order_team[rank+1:]:
            graph[team_num][low_team_num] = 1

    M = int(input())
    new_indegree = indegree[:]
    for _ in range(M):
        a_team,b_team = map(int,input().split())
        if indegree[a_team] > indegree[b_team]:
            a_team,b_team = b_team,a_team

        # a_team이 상위권 b_team이 하위권 원래는
        graph[b_team][a_team] = 1
        graph[a_team][b_team] = 0
        new_indegree[a_team] += 1
        new_indegree[b_team] -= 1
    indegree = new_indegree[:]
    stack = deque()

    for team_num in range(1,N+1):
        if not indegree[team_num]:
            stack.append(team_num)
    result = []
    if len(stack) == 1:
        cnt = 0
        while cnt<N:
            if not len(stack):
                result = 'IMPOSSIBLE'
                break
            elif len(stack) > 1:
                result = '?'
                break

            cur_node = stack.popleft()
            result.append(cur_node)
            for next_node in range(1,N+1):
                if graph[cur_node][next_node]:
                    indegree[next_node] -= 1
                    if not indegree[next_node]:
                        stack.append(next_node)
            cnt += 1
    elif len(stack) == 0:
        result = 'IMPOSSIBLE'
    else:
        result = '?'
    if type(result) == list:
        print(*result)
    else:
        print(result)

이 문제는 최근에 풀었던 문제 중에서 문제를 이해하는데 가장 힘들었던 문제였다. 문제를 이해하고 보면,

쉽게 이해가 가능한 문제이다.

문제에 주어진 N개의 숫자는

앞에서부터 1등부터 N등까지를 표현한 것이다.

그리고 그 각 자리에 있는것이 1등을 한 팀 N_1  2등을 한 팀 N_2 이런식인것이다.

그러면 문제에 첫 예제로 주어진

5 4 3 2 1

1등은 5팀

2등은 4팀

3등은 3팀

4등은 2팀

5등은 1팀

이 된것이다. 그렇다는 것은 이걸 그래프적으로 표현을 하면 다음과 같다.

 다음 과 같이 표현을 할 수 있을 것이다.

5팀이 가장 루트 노드이고, 이 5팀을 지나가고 난뒤에 4팀 3팀 2팀 1팀을 순서적으로 할 수 있는것이다.

그러면 여기서 상대적인 등수가 바뀌었다는 것은

저 그래프에서의 순서가 뒤바뀐다는 것을 의미하게 된다.

그러면 첫번째 예제에선

2 4

3 4 라는 입력이 주어졌다.

그러면

빨갛게 동그라미 모양이 된 화살표가 반대로 가게 되는것이다.

즉 녹색화살표 처럼 반대로 표시가 바뀌게 된것이다.

그러면 이때의 순위는

5 -> 3->2->4->1 순서가 되는 것을 알 수 있다.

그래서 이 문제에서 중요한 것은

처음 입력이 주어졌을때 자기 등수보다 이하의 등수들에게 부모 자식 관계를 나타내느 그래프 간선을 그려준다.

그리고 난뒤에 m개의 상대적인 순위가 바뀌었다는 입력이 들어오면

서로원래의 rank를 확인해서

높은 랭크 -> 낮은 랭크로 연결되어있던 간선을 반대로 바꾸어주고,

우리가 간선을 들어온 개수를 세어놓은 indegree 수치를

낮은 순위는 1개를 줄여주고, 높은 순위는 1개를 높여주면 된다.

그리고 여기서 주의해야할 것은 바로 값을 바꾸면 바뀐 순위를 참조가 가능하므로,

복사된 배열에서 값을 변경시키고 나중에 옮겨줘야한다.

그리고 정상적인 위상정렬을 시행해주면 된다.

만약에 스택이 비게되면 사이클이 발생한 것이므로,  impossible을

스택에 길이가 2개이상이 된다는것은 같은 rank에 2개가 있게 되는 것이므로, ?를 출력하게 해주면 된다.

import sys

input = sys.stdin.readline

for _ in range(int(input())):
    N = int(input())

    prev_rank = [0]*(N+1)
    current_rank = [0]*(N+1)
    arr = list(map(int,input().split()))
    for i in range(N):
        prev_rank[arr[i]] = i +1
        current_rank[arr[i]] = i + 1

    M = int(input())

    for _ in range(M):
        a_team,b_team = map(int,input().split())

        if prev_rank[a_team] > prev_rank[b_team]:
            current_rank[a_team] -= 1
            current_rank[b_team] += 1
        else:
            current_rank[a_team] += 1
            current_rank[b_team] -= 1

    result = [0]*(N+1)
    flag= False
    for team_num in range(1,N+1):
        if result[current_rank[team_num]]:
            flag = True
            break
        else:
            result[current_rank[team_num]] = team_num

    if flag:
        print('IMPOSSIBLE')
    else:
        print(*result[1:])

 이건 좀 더 간단한 풀이이다.

 하지만 이 풀이는 ?인 경우가 없다고 가정하고 푼 것이다.

import sys
from collections import deque

input = sys.stdin.readline


N,M = map(int,input().split())
graph = [set() for _ in range(N+1)]
degree = [0 for _ in range(N+1)]
for _ in range(M):
    pdN,*arr = list(map(int,input().split()))

    for i in range(pdN-1):
        x,y = arr[i],arr[i+1]
        if y not in graph[x]:
            graph[x].add(y)
            degree[y] += 1

stack = deque()
cnt = 0
result = []
flag = True

for i in range(1,N+1):
    if degree[i]==0:
        stack.append(i)
while cnt<N:
    if not stack:
        flag = False
        break
    node = stack.popleft()
    result.append(str(node))
    for next_node in graph[node]:
        degree[next_node] -= 1

        if degree[next_node] == 0:
            stack.append(next_node)
    cnt += 1

if flag:
    print('\n'.join(result))
else:
    print(0)

이 문제와 같은 경우 평범한 위상정렬이다.

여러명의 PD를 통해 앞에서부터, 하나씩 그래프에 SET으로 넣어주었다.

그리고 degree가 0인것들은 최초의 stack에 넣어주고 난뒤에 위상정렬을 구해주면서,

사이클이 발생할 시, 음악프로그램을 구할 수 없는 것이므로, 그때 flag로 분기 처리를 해주었다.

그리고 stack에 나온순서대로 result에 넣어주고 출력을 해주었다.

import sys

input = sys.stdin.readline
N = int(input())
M = int(input())

graph = [[0 for _ in range(N+1)] for i in range(N+1)]
visited = [[True for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x][y] = 1



for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if start == end:
                continue
            if graph[start][mid] and graph[mid][end]:
                graph[start][end] = 1

result = []
for start in range(1,N+1):
    cnt = 0
    for end in range(1,N+1):
        if start == end:
            continue
        else:
            if not (graph[start][end] or graph[end][start]):
                cnt += 1
    result.append(cnt)
for row in result:
    sys.stdout.write(str(row)+'\n')

많이 해맸던 문제였다. 대소관계가 있는데 그걸 통해, 서로 비교가 불가능한 경우를 찾는 것을 어떻게 할지 고민을 많이했다.

플로이드 와샬을 통해 만들었다. 

대소 관계가 가능하다는 것은 

(1,2) (2,3) 이렇게 주어진다하면

그래프에서 graph[1][2],graph[2][3]에 1이 들어갈것이다.

그러면 플로이드 와샬을 통해, 두개의 그래프가 graph[start][mid], graph[mid][end] 가 전부 1이라고 했을때에만

start 가 end보다 크다는것을 알 수 있다.

이렇게 플로이드 와샬을 돌리고 난뒤에, 전체 N에 대해서 N번 돌려주면서, 서로 다른 두점의 그래프의 값이 전부 0이면, 

대소비교가 불가능한 경우이다. 이 경우를 전부 세어주면 문제를 풀 수 있다.