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()
 
 
def find_parents(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parents(make_set[ind])
    return make_set[ind]
 
def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)
    if ranks[X] < ranks[Y]:
        X,Y = Y,X
    make_set[Y] = X
    if ranks[X] == ranks[Y]:
        ranks[X] += 1
 
 
N,M = map(int,input().split())
 
arr = [0] + list(input().split())
weight_list = []
for _ in range(M):
    x,y,pay = map(int,input().split())
    if arr[x] != arr[y]:
        weight_list.append((pay,x,y))
 
weight_list.sort(reverse=True)
make_set = [i for i in range(N+1)]
ranks = [1 for _ in range(N+1)]
 
cnt = 0
result = 0
while weight_list:
    pay,x,y = weight_list.pop()
    X,Y = find_parents(x), find_parents(y)
 
    if X != Y:
        union(X,Y)
        cnt += 1
        result += pay
    if cnt == N-1:
        break
 
if cnt != N-1:
    print(-1)
else:
    print(result)

이 문제는 처음부터 간선을 저장할때 두 노드가 남초+여초인 조합인 경우에만 저장을 해서 크루스칼을 해주면 된다.

그리고 크루스칼을 진행하고, 전체 cnt의 개수가 N-1이 안되는 경우에는 전부 연결이 안되는 경우이니 -1을 출력해주고

같을 때에는 result를 출력해주면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
def union(a,b):
    A = find_parent(a)
    B = find_parent(b)
    if A != B:
        if rank[A] < rank[B]:
            A,B = B,A
        make_set[B] = A
        if rank[A] == rank[B]:
            rank[A] += 1
        return True
    return False
 
def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    else:
        make_set[ind] = find_parent(make_set[ind])
        return make_set[ind]
 
def kruskal():
    value = 0
    for p,x,y, in weight_list:
        if union(x,y):
            value += 1^p
    return value
 
 
N,M = map(int,input().split())
weight_list = []
for _ in range(M+1):
    x,y,p = map(int,input().split())
    weight_list.append((p,x,y))
make_set = list(range(N+1))
rank = [1]*(N+1)
weight_list.sort()
a = kruskal()
weight_list.sort(reverse=True)
make_set = list(range(N+1))
rank = [1]*(N+1)
b = kruskal()
print(a**2-b**2)

이 문제는 크루스칼을 활용해서 풀면 되는 문제이고, 크루스칼에 사용되는 간선을 오름차순과 내림차순으로 각각 정렬해서 

그때 크루스칼을 해서 값을 구한뒤 제곱값을 빼주면딘다.

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
 
 
def input():
    return sys.stdin.readline().rstrip()
 
 
def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]
 
 
def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)
 
    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
 
 
T = int(input())
 
 
for tc in range(1,T+1):
    N = int(input())
    make_set = [i for i in range(N)]
    ranks = [1 for _ in range(N)]
 
    for _ in range(int(input())):
        x,y = map(int,input().split())
        union(x,y)
    print(f'Scenario {tc}:')
    for _ in range(int(input())):
        x,y = map(int,input().split())
        if find_parents(x) != find_parents(y):
            print(0)
        else:
            print(1)
 
    if tc != T:
        print()

전형적인 분리집합 문제였다.

들어오는 입력대로 union을 해주었고, 서로의 부모가 다를시에는 0 같을 시에는 1이 출력되게 했다.

import sys
import heapq
 
def input():
    return sys.stdin.readline().rstrip()
 
def solution():
    priority_que = []
    for num in range(1,N+1):
        if not indegree[num]:
            priority_que.append(num)
    heapq.heapify(priority_que)
 
    result = []
    while priority_que:
        num = heapq.heappop(priority_que)
        result.append(num)
        for next_num in graph[num]:
            indegree[next_num] -= 1
            if not indegree[next_num]:
                heapq.heappush(priority_que,next_num)
    return result
 
N,M = map(int,input().split())
 
graph = [ [] for _ in range(N+1)]
indegree = [0 for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
    indegree[y] += 1
 
print(*solution())

문제를 읽어보면 순서가 정해져있고, 앞선 문제를 풀어야지 뒤의 문제를 풀 수 있다고 되어 있다.

이 문구를 보고 위상정렬임을 알 수 있고, 위상정렬 해주면 된다.

문제 난이도가 골드2 이지만, 골드2 수준은 아닌 듯한 문제였다. queue 대신 heapq를 쓰면 풀리는 문제라,

위상 정렬에 대해 알고 있으면 쉽게 풀릴 수 있는 문제라 생각한다.

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
from collections import deque
input = sys.stdin.readline
 
def bfs(x,y):
 
    queue = deque()
    queue.append((x,y))
    visited[x][y] = False
    while queue:
        x,y = queue.popleft()
 
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if visited[nx][ny] and arr[nx][ny] >= T:
                    visited[nx][ny] = False
                    queue.append((nx,ny))
 
 
N,M = map(int,input().split())
 
arr = []
 
for x in range(N):
    input_list = list(map(int,input().split()))
    temp = []
    for k in range(M):
        temp.append(sum(input_list[3*k:3*(k+1)]))
 
    arr.append(temp)
 
T = int(input())
 
T = 3*T
 
 
visited = [[True for _ in range(M)] for _ in range(N)]
 
dx = [-1,1,0,0]
dy = [0,0,-1,1]
 
cnt = 0
for x in range(N):
    for y in range(M):
        if arr[x][y] >= T  and visited[x][y]:
            bfs(x,y)
            cnt += 1
 
print(cnt)

이 문제는 처음들어올때부터 값을 계산해주는 방식으로 했다.

이 문제를 평균값을 구하면 float 값이 나올것 같아서, 어차피 문제에서 경계값이 정수이고,

한 픽셀을 구성하는 것은 3개로 고정적이므로 처음에 들어올때 열을 기준으로 3개씩 짤라주면서 그때의 합을 전부 저장하는 방식으로 했다.

이렇게 변형햔 배열을 가지고 BFS를 하면 되는데

계산의 편의성을 위해 경계값이 들어오자마자 그냥 3배를 해주었다.

그리고 난뒤에는 일반적인 BFS,DFS를 해주면 되는 문제이다.

방문을 하지않고, 경계값을 넘는 위치에 대해 bfs를 해서 인접한 픽셀들을 구하고, 함수가 끝난뒤에 개수를 늘려주었다.