Coding 공부

import sys

def input():
    return sys.stdin.readline().rstrip()
def floyd():
    result = 0
    for mid in range(N):
        for start in range(N):
            for end in range(N):
                if start == end or end == mid or mid == start or start>end:continue
                if arr[start][end] == arr[start][mid] + arr[mid][end]:
                    if (start,end) in edge_list:
                        edge_list.remove((start,end))
                if arr[start][end] > arr[start][mid] + arr[mid][end]:
                    return -1

    for x,y in edge_list:
        result += arr[x][y]
    return result
N = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
edge_list = set()
for i in range(N):
    for j in range(N):
        if i ==j or i>j: continue
        edge_list.add((i,j))

print(floyd())

이 문제는 이해하기 어려웠던 문제였다.

이 문제를 읽어 보면 강호는 모든 쌍의 도시에 대해서 최소 이동시간을 구해놓았다고 했다.

그리고 민호는 이 표를 보고 원래 도로가 몇개 있는지를 구해보려고 한다고 적혀있다.

그러면 예제에 있는 도시 1-2, 2-3, 1-4, 3-4, 4-5, 3-5를 연결하는 도로만 있다고 가정해도,

강호가 구한 모든 쌍의 최솟값을 구할수 있다고 했다.

이 부분을 통해 유추를 해야한다.

원래는 여러 도로가 있었겠지만, 강호는 모든 쌍의 도시에 대해서 최소 이동시간을 구했기 때문에,

불 필요한 다른 도로들을 없애버린것이다.

즉 1->3 까지의 시간이 15인데 이것은 1->2 와 2->3을 더한 값과 동일하다.

1->5 또한 1->4 4->5를 더한 값과 동일하다.

즉 A라는 도시에서 B라는 도시를 갈때 A->C + C->B를 만족하는 경우가 있으면, A->B의 도로는 없어도, 동일한 시간 내에 갈 수 있으므로,

도로의 개수를 최솟값을 구할때 제외해도 된다.

이 부분을 주의해서 문제를 풀어주면 된다.

먼저 모든 도로들을 넣어주어야하는데, A->B와 B->A는 동일 하므로,

A<B를 만족하는 도로들을 먼저 edge_list에 전부 넣어준다.

그러면서 플로이드 와샬을 하면서

arr[start][end] == arr[start][mid] + arr[mid][end] 를 만족하는 경우엔, edge_list에서 그 도로를 제외 해준다.

또한 우리는 A<B인 경우만 하도록 했으므로, start> end 이거나, start or end 가 mid와 동일할때는 제외하고 검사해준다.

그리고 여기서 또 구해야하는 또 다른 경우는 불가능한 경우에 -1을 출력하는 조건이 있다.

이 조건을 만족하는 경우는 도시에서 다른 도시까지 가는 시간의 최소값이 갱신 되는 경우이다.

갱신 되었을 때에는 -1을 반환해주고, 아닌 경우에는 남은 edge_list를 통해 모든 도로의 시간의 합을 구하면 된다.

import sys
def input():
    return sys.stdin.readline().rstrip()
N,M,R = map(int,input().split())
arr = [0] + list(map(int,input().split()))

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


INF = float('inf')
distance = [[0 if i == j else INF for j in range(N+1)] for i in range(N+1)]
for _ in range(R):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,float('inf')), pay)
    graph[y][x] = min(graph[y].get(x, float('inf')),pay)
    distance[x][y] = min(distance[x][y],pay)
    distance[y][x] = min(distance[y][x],pay)

value = [0 for _ in range(N+1)]
for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if distance[start][end] > distance[start][mid] + distance[mid][end]:
                distance[start][end] =  distance[start][mid] + distance[mid][end]


result = 0
for node in range(1,N+1):
    temp = 0
    for next_node in range(1,N+1):
        if distance[node][next_node] <= M:
            temp += arr[next_node]
    if temp > result:
        result = temp
print(result)

이 문제는 플로이드와샬을 통해 최단거리를 갱신해주고, 

N^2를 탐색하면서, 거리가 M 이하일때 더해줘서 최대값을 갱신해서 출력해주는 문제이다.

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()
def path(s,e):
    if next_node[s][e] == None:
        return [0]
    else:
        result = [s]
        while s != e:
            s = next_node[s][e]
            result.append(s)
        return result
N = int(input())
M = int(input())
INF = float('inf')
distance_list = [[0 if i==j else INF for j in range(N+1)] for i in range(N+1)]

next_node = [[None for _ in range(N+1)] for _ in range(N+1)]
graph = [{} for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    if distance_list[x][y] > pay:
        distance_list[x][y] = pay
        next_node[x][y] = y


for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if distance_list[start][end] > distance_list[start][mid] + distance_list[mid][end]:
                distance_list[start][end] = distance_list[start][mid] + distance_list[mid][end]
                next_node[start][end] = next_node[start][mid]


for i in range(1,N+1):
    print(*[val if val != INF else 0 for val in distance_list[i][1:]])


for start in range(1,N+1):
    for ends in range(1,N+1):
        if distance_list[start][ends] == INF:
            print(0)
        else:
            answer = path(start,ends)
            if len(answer) == 1:
                print(0)
            else:
                print(len(answer),*answer)

플로이드 와샬을 이용해서 풀어야하는데

여기서 중요한 점은 이동지점을 추적해야한다.

그 방법은 start-> end까지 갈때 들리는 노드를 갱신을 해주는 것이다.

a->b로 갈때 b로 간다고 저장을 해놨을때

중간에 값을 갱신한 mid가 있으면

a->b에 b가 아닌 mid를 저장해준다.

이렇게 함으로서

end_node가 동일한 것이 나올때까지 계속 반복을 해주면 되는 것이다.

플로이드 와샬은 자주 사용했지만, 경로를 구해본적은 처음이여서 힘들었다.

이 부분은 외우고 나중에 사용할 수 있도록 노력해야겠다.

import sys

input = sys.stdin.readline

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


INF = float('inf')
graph = [[0 if x == y else INF for y in range(N+1)] for x in range(N+1)]

for _ in range(M):
    x,y,pay = map(int,input().split())

    graph[x][y] = min(graph[x][y],pay)




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

K = int(input())
friend_list = list(map(int,input().split()))
min_value = INF
min_list = []
for city in range(1,N+1):
    temp_max = 0
    for p_num in friend_list:
        if graph[p_num][city] + graph[city][p_num] > temp_max:
            temp_max = graph[p_num][city] + graph[city][p_num]

    if temp_max < min_value:
        min_value = temp_max
        min_list = [city]
    elif temp_max == min_value:
        min_list.append(city)

print(*min_list)

 이 문제는 플로이드와샬을 이용해 모든 경로에 대해 이동비용을 먼저 계산을 해준다.

그리고 전체 도시들을 for문을 돌리면서, 친구들의 이동비용을 구하고,

각 친구들의 이동비용의 최대값의 최소가 되는 경우를 구해서 출력해주면 된다.

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이면, 

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

import sys
import collections
input = sys.stdin.readline

def bfs1(x):
    que=collections.deque()
    que.append(x)
    temp=set()
    temp.add(x)
    while que:
        node=que.popleft()
        for i in graph1[node]:
            if i not in temp:
                temp.add(i)
                visit[x]+=1       
                que.append(i)
    return
def bfs2(x):
    que=collections.deque()
    que.append(x)
    temp=set()
    temp.add(x)
    while que:
        node=que.popleft()
        for i in graph2[node]:            
            if i not in temp:
                temp.add(i)
                visit[x]+=1       
                que.append(i)
    return
 

N,M = map(int,input().split())
arr=[list(map(int,input().split())) for i in range(M)]
graph1=[[] for i in range(N+1)]
graph2=[[] for i in range(N+1)]
for i in arr:
    graph1[i[0]].append(i[1])
    graph2[i[1]].append(i[0])
visit=[0]*(N+1)
for i in range(1,N+1):        
    bfs1(i)
    bfs2(i)

cnt=visit.count(N-1)
print(cnt)

import sys

input = sys.stdin.readline
n = int(input())
INF = float('inf')
graph = [[INF if i !=j else 0 for j in range(n)] for i in range(n)]
m = int(input())

for _ in range(m):
    A,B,C = map(int,input().split())
    graph[A-1][B-1] = min(graph[A-1][B-1],C)
for k in range(n):
    for start in range(n):
        for end in range(n):
            if graph[start][end] > graph[start][k] + graph[k][end]:
                graph[start][end] = graph[start][k] + graph[k][end]



for row in graph:
    print(*[j if j != INF else 0 for j in row])

플로이드 와샬을 이용한 문제였다.

2차원 배열을 자기자신을 가는 경우를 제외한 나머지 경우를 INF로 초기화 시켜주고, 들어오는 input에서도 같은 경로를 여러번 들어오는 경우가 있으므로, 최소값으로 넣어주었다.

그리고 플로이드 와샬을 3중 for문으로 구현해줬다.

출력은 if else문을 이용해 INF가 그대로인 곳은 갈수 없는 곳이므로 0으로 출력해주었다.

import heapq


def solution(n, s, a, b, fares):
    answer = float('inf')
    total_node = set(range(1,n+1))
    graph = [{} for i in range(n+1)]
    for start,end,fee in fares:
        graph[start][end] = fee
        graph[end][start] = fee
    def distra(start,end):
        nonlocal graph,n
        node_list = []
        heapq.heappush(node_list,(0,start))
        INF = float('inf')
        Fee_list = [INF]*(n+1)
        Fee_list[start] = 0
        while node_list:
            fee,node = heapq.heappop(node_list)
            if fee > Fee_list[node]:
                continue
            if node == end:
                return fee
            for next_node in graph[node]:
                temp_fee = fee + graph[node][next_node]
                if Fee_list[next_node]> temp_fee:
                    Fee_list[next_node] = temp_fee
                    heapq.heappush(node_list,(temp_fee,next_node)) 
        return INF
        
    for k in total_node:
        answer = min(answer,distra(s,k)+distra(k,a)+distra(k,b))
    return answer

solution(7,3,4,1,[[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]])

처음엔 다익스트라로 만들어서 풀었다. 이 풀이의 문제점은 한번했던 다익스트라를 계속하기 때문에, 시간이 오래걸리는 문제가 있었다.

import heapq


def solution(n, s, a, b, fares):
    answer = float('inf')
    INF = float('inf')
    graph = [[INF if x!=y else 0 for x in range(n+1)] for y in range(n+1)]
    for start,end,fee in fares:
        graph[start][end] = fee
        graph[end][start] = fee

    for mid in range(1,n+1):
        for start in range(1,n+1):
            for end in range(1,n+1):
                if graph[start][end] > graph[start][mid] + graph[mid][end]:
                    graph[start][end] = graph[start][mid] + graph[mid][end] 
        
    for k in range(1,n+1):
        answer = min(answer,graph[s][k]+graph[k][a]+graph[k][b])
    return answer

 위의 문제가 매번 다읷트라를 계산하는것을 벗어나기 위해 플로이드 와샬로 각 노드에서 다른노드까지의 최저비용을 갱신해놓고, 그 합의 최저값을 구하는 방식으로 했다.

import heapq

def solution(n, s, a, b, fares):
    answer = float('inf')
    INF = float('inf')
    graph = [{} for i in range(n+1)]
    for start,end,fee in fares:
        graph[start][end] = fee
        graph[end][start] = fee
    Fee_list = [[INF]*(n+1) for _ in range(3)]
    def distra(start,idx):
        nonlocal graph,n,Fee_list
        node_list = []
        heapq.heappush(node_list,(0,start))
        Fee_list[idx][start] = 0 
        while node_list:
            fee,node = heapq.heappop(node_list)
            if fee > Fee_list[idx][node]:
                continue
            for next_node in graph[node]:
                temp_fee = fee + graph[node][next_node]
                if Fee_list[idx][next_node]> temp_fee:
                    Fee_list[idx][next_node] = temp_fee
                    heapq.heappush(node_list,(temp_fee,next_node)) 
    distra(s,0)
    distra(a,1)
    distra(b,2)
    for mid in range(1,n+1):
        temp = Fee_list[0][mid] + Fee_list[1][mid] + Fee_list[2][mid]
        if answer > temp:
            answer = temp
    return answer


solution(7,3,4,1,[[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]])

마지막은 www.youtube.com/watch?v=FX9n1PFv2K4 유튜브의 barkingdog님의 풀이를 참조해서 푼 방식이다.

제일 첫번째의 매번 다익스트라를 하던것을 총 3번의 다익스트라로 그 값들을 전부 저장해놓고 푸는 방식이다.

자세한 설명은 유튜브를 참조하길 바란다.