Coding 공부

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에 도착하면 현재까지 누적된 값과 최대값과 비교를 해서 더 큰 값을 넣어주면 된다.

N = int(input())

arr = list(map(int,input().split()))

arr.sort()
min_value = 0
if len(arr)%2:
    min_value = arr.pop()
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
else:
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
print(min_value)

정렬을 해주고, 가장 첫번째값과 가장끈값을 더한값의 최소값을 출력해주면 된다.

import sys

input = sys.stdin.readline
def dfs(node,flag,*args):
    stack = [(node,0)]
    distance_list = [0 for _ in range(N+1)]
    visited = [False for _ in range(N+1)]
    visited[node] = True
    if not flag:
        visited[args[0]] = True
    while stack:
        node,distance = stack.pop()
        distance_list[node] = distance

        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                stack.append((next_node,distance+graph[node][next_node]))
    
    temp = []

    for i in range(1,N+1):
        temp.append((distance_list[i],i))
    temp.sort(key=lambda x :-x[0])
    if flag:
        return_value = temp[0][1]
    else:
        return_value = temp[0][0]
    return return_value


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

first_point = dfs(1,True)
second_point = dfs(first_point,True)

first_value = dfs(first_point,False,second_point)
second_value = dfs(second_point,False,first_point)

print(max(first_value,second_value))

 이 문제는 트리의 지름을 구하는 방법을 응요한 문제이다.

총 4번의 dfs를 통해 두번째 트리의 지름을 알 수 있다.

첫번째 dfs를 통해 아무지점에서 가장 먼 지점을 구한다.

이 지점은 지름을 구성하는 한 점이 될것이다.

두번째 dfs를 통해 첫번째 dfs에서 구한 점에서 가장 먼 점을 구한다.

그러면 이 점은 트리의 지름을 구성하는 가장 먼 점이 될것이다.

이렇게 2번의 dfs를 통해 우리는 가장 먼 점 2개를 구했다.

그러면 이 2점을 각각 dfs를 돌려, 가장 먼 점에서 2번째인 것을 찾아낸다.

그리고 이렇게 두 거리를 구한 뒤 그 중에 더 큰 점을 선택하면 되는 문제이다.

import sys

input = sys.stdin.readline
def dfs(node):
    distance_list = [0 for _ in range(N+1)]
    visited = [False for _ in range(N+1)]
    visited[node] = True
    stack = [(node,0)]
    while stack:
        node,distance = stack.pop()
        distance_list[node] = distance
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                stack.append((next_node,graph[node][next_node]+distance))
    return distance_list

N = int(input())
graph = [{} for _ in range(N+1)]

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


distance1 = dfs(1)
far_point1 = distance1.index(max(distance1))
distance2 = dfs(far_point1)
far_point2 = distance2.index(max(distance2))
distance3 = dfs(far_point2)
result = sorted(distance2+distance3)[-3]
print(result)

단 3번의 dfs를 통해 구하는 방법도 있다.

이 방법은 지름을 구성하는 2점의 전체길이를 한 리스트로 정하고 뒤에서 3번째를 출력해주는 것이다.

왜냐하면 한 리스트당 한 지점에서 가장 먼 지점은 서로 자신들이기 때문에, 그 2점을 제외하고 그 다음번으로 큰 것이

두번째 트리의 지름의 답이된다.

from collections import deque
def bfs(red,blue):
    stack = deque()

    stack.append((*red,*blue,0,''))
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    direction = ['U','D','L','R']
    while stack:
        rx,ry,bx,by,dis,route = stack.popleft()

        if dis >= 10:
            return (-1,'-')

        for i in range(4):
            nrx,nry = rx,ry
            r_p = 0
            while 0<=nrx<N and 0<=nry<M and arr[nrx][nry] != '#' and arr[nrx][nry] != 'O':
                nrx += dx[i]
                nry += dy[i]
                r_p += 1
            nbx,nby = bx,by
            b_p = 0
            while 0<=nbx<N and 0<=nby<M and arr[nbx][nby] != '#' and arr[nbx][nby] != 'O':
                nbx += dx[i]
                nby += dy[i]
                b_p += 1

            if (nbx,nby) == (nrx,nry):
                if arr[nbx][nby] == 'O':
                    continue
                if r_p > b_p:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]

            elif arr[nbx][nby] == 'O':
                continue
            elif arr[nrx][nry] == 'O':
                return (dis+1,route + direction[i])
            nrx -= dx[i]
            nry -= dy[i]
            nbx -= dx[i]
            nby -= dy[i]
            if not visited[nrx][nry][nbx][nby]:continue
            visited[nrx][nry][nbx][nby] = False
            stack.append((nrx,nry,nbx,nby,dis+1,route+direction[i]))
    return (-1,'-')

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


arr = []
blue = []
red = []
for x in range(N):
    temp = list(input())
    for y in range(M):
        if temp[y] == 'B':
            blue = (x,y)
        elif temp[y] == 'R':
            red = (x,y)
    arr.append(temp)


visited = [[[[True for _ in range(M)] for _ in range(N)] for _ in range(M)] for _ in range(N)]


result = bfs(red,blue)
if result[0] != -1:
    print(result[0])
    print(result[1])
else:
    print(result[0])

 이 문제는 사실상 구슬탈출 2와 동일한 문제이다.

구슬 탈출2와 달라진점은 이동방향을 저장시키는 것외에는 없다.

문제를 푸는 방식은 다음과 같다.

먼저 방문배열을 4차원 배열로 만들어준다.

그 이유는, 빨간색공이 안 움직이지만, 파란공만 움직이는 경우도 있고,

파란공만 움직이고, 빨간공이 움직이지 않을때가 있으므로, 구분을 하기위해 4차원 배열을 선언을 해주었다.

그리고 BFS를 하는 과정은 다음과 같다. 한 방향으로 정하고 각가 red ball과 blue ball을

구멍 혹은 벽을 만나기전까지 계속 굴려준다.

그러면 최종적으로 위치하곳은 벽 혹은 구멍일 것이다. 이 과정에서 각각의 움직이는 횟수도 세어주었다.

먼저 구멍에 빠졌는지 확인을 해주자.

파란공과 빨간공이 전부 빠졌다면, 이것은 패배한것이므로, 제외를 해주자.

그리고 파란공만 들어간거면 그것 또한 패배한 것이므로, 제외를 하자.

그리고 빨간공만 들어갔을때에는 그때는 이긴것이므로, 지금까지 누적된 이동경로를 반환을 해주면 된다.

그리고 두 공의 위치가 최종적으로 같다면, 둘중 먼저 해당지점에 먼저와있는지가 중요하다.

우리는 위에서 반복횟수를 세어주었다.

반복 횟수가 적다는것은 더 빨리 도착한 것이므로, 반복횟수가 많은 볼을 한칸 뒤로 빼준다.

이러한 작업을 다 마치고 나면 위에서 우리는 벽이나 구멍외에는 멈추지 않았다.

그러면 현재 볼들이 있는 위치는 벽일테니, 뒤로 한칸씩 동일하게 이동해준다.

이렇게 한뒤에, 우리가 방문하지 않은 곳이면 방문표시를하고 stack에 넣어주면 된다.

이 문제는 방문을 어떻게 할것인가, 그리고 공을 굴릴때 어떻게 한번에 끝까지 굴릴것인가. 그리고 같은 위치에

중첩됬을때 어떻게 해결하는지 중요한 문제였다.

import sys

def find_agent(agent,task):
    if agent == N:
        return 1
    
    if dp[task] != -1:
        return dp[task]

    for i in range(N):
        if not (task & 1<<i):

            temp = find_agent(agent+1,task|1<<i)*arr[agent][i]/100
            if temp > dp[task]:
                dp[task] = temp
    
    return dp[task]
input = sys.stdin.readline
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]


dp = [-1 for _ in range(2**N+1)]




find_agent(0,0)

print(dp[0]*100)

문제를 푸는방식은 다음과 같다. 

각 task를 비트로 구분을 하게 한다.

이 문제에서 최대 20개의 임무가 있으므로, 2^20으로 비트를 구분해낼수 있다.

이러한 점을 이용해, 각자리의 비트는 그와 대응되는 일을 맡는것으로 가늠할 수 있다.

그래서 우리는 재귀를 이용해, 현재까지 선택된 task에서 선택되지 않은 task를 선택해 재귀를 한뒤,

그 결과값들을 최대값으로 갱신을 해주면 되는 문제이다.

또한 중복되는 일을 방지하고자, task별로 값을 저장한뒤에 그 값이 초기값이 아니면 되돌려주는 작업을 해주었다.

import sys
import heapq
input = sys.stdin.readline
def dijkstra_fox():
    distance = [INF for _ in range(N+1)]

    distance[1] = 0
    node_list = []
    heapq.heappush(node_list,(0,1))

    while node_list:
        dis,cur_node = heapq.heappop(node_list)
        if distance[cur_node] < dis:
            continue

        for next_node in graph[cur_node]:
            
            if distance[next_node] > graph[cur_node][next_node] + dis:
                distance[next_node] = graph[cur_node][next_node] + dis
                heapq.heappush(node_list,(distance[next_node],next_node))
    return distance


def dijkstra_wolf():
    distance = [[INF for _ in range(N+1)] for _ in range(2)]
    distance[1][1] = 0
    node_list = []
    heapq.heappush(node_list,(0,1,1))

    while node_list:
        dis,cur_node,turn = heapq.heappop(node_list)
        turn = turn%2
        next_turn = (turn+1)%2
        if distance[turn][cur_node] < dis:
            continue
        for next_node in graph[cur_node]:
            if turn:
                next_distance = dis + graph[cur_node][next_node]//2
            else:
                next_distance = dis + graph[cur_node][next_node]*2
            
            if distance[next_turn][next_node] > next_distance:
                distance[next_turn][next_node] = next_distance
                heapq.heappush(node_list,(next_distance,next_node,next_turn))
    return distance
N,M = map(int,input().split())

graph = [{} for _ in range(N+1)]

for _ in range(M):
    x,y,d = map(int,input().split())
    graph[x][y] = d*2
    graph[y][x] = d*2

INF= float('inf')




distance_fox = dijkstra_fox()
distance_wolf = dijkstra_wolf()
result = 0
for i in range(2,N+1):
    if distance_fox[i] < distance_wolf[0][i] and distance_fox[i] < distance_wolf[1][i]:
        result += 1

print(result)

어려웠던 문제였다.

 이 문제는 다음과 같이 풀면된다. wolf일때 2개의 turn으로 나누어서 distance에 저장을 시켜준다.

현재 turn의 distance에 저장하는 것이 아닌 next_turn에 저장을 하고 그 값을 비교하는 것에 조심해주면 된다.

그리고 제일 주의해야할 것은 가장 처음 시작하는 노드를 0으로 초기화할때 가장 첫턴 1턴 1번 노드만 0으로

초기화 시켜야 한다

이를 지키지 않고 둘다 초기화 시키면,, 틀렸습닏를 볼 수 있을 것이다.

def dfs(cnt,goal,res):
    if cnt == goal:
        print(*res)
        return
    else:
        for i in range(N):
            if visited[i]:
                temp = res + [arr[i]]
                if tuple(temp) not in record:
                    visited[i] = False
                    record.add(tuple(temp))
                    dfs(cnt+1,goal,temp)
                    visited[i] = True


N,M = map(int,input().split())
visited = [True]*N
record = set()
arr = list(map(int,input().split()))

arr.sort()


dfs(0,M,[])

문제 자체는 어렵지 않은 문제이다. 조합을 이용해서 문제를 풀어주면 된다.

그리고 RECORD를 이용해서 중복되는 경우를 배제해줬다.

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를 구한뒤 결과값에 더해주면 된다.