[알고리즘공부] [자료구조공부] 플로이드-와샬 알고리즘

Floyd-Warshall

카테고리 : Study >> Codingtest tag #Codingtest

🎀 본 게시물은 코딩테스트를 위한 자료구조, 알고리즘 공부 게시물입니다. 또한 다음 강의자료를 사용했음을 알려드립니다. 인프런강의 🎀


플로이드-와샬 알고리즘에 대해 알아보고 예시 문제를 통해 익히자.

플로이드-와샬 알고리즘이 뭐지?

컴퓨터 과학에서 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 $R$의 추이적 폐포를 찾거나, 가중 그래프의 모든 꼭짓점 쌍 간의 최대 폭 경로를 (슐츠 선거 제도와 결합해서) 찾는 것이 가능하다.

1. 도시 이동 비용

N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최소값을 구하는 프로그램을 작성하 세요.

그림1

▣ 입력설명

첫 번째 줄에는 도시의 수 $N(N<=100)$과 도로수 $M(M<=200)$가 주어지고, $M$줄에 걸쳐 도로정보와 비용(20 이하의 자연수)이 주어진다. 만약 1번 도시와 2번도시가 연결되고 그 비용이 13이면 “1 2 13”으로 주어진다.

▣ 출력설명

모든 도시에서 모든 도시로 이동하는데 드는 최소 비용을 아래와 같이 출력한다. 자기자신으로 가는 비용은 0입니다. i번 정점에서 j번 정점으로 갈 수 없을 때는 비용을 “M”으 로 출력합니다.

▣ 입력예제 1

5 8
1 2 6
1 3 3
3 2 2
2 4 1
2 5 13
3 4 5
4 2 3
4 5 7

▣ 출력예제 1

0 5 3 6 13
M 0 M 1 8
M 2 0 3 10
M 3 M 0 7
M M M M 0

설명

  • 그림을 표로 만든다.
  • i도시에서 j도시로 가는 비용을 dy[i][j]에 넣는다.
  • i도시에서 j도시로 갈 때 k도시를 거치는 경우는 dy[i][k] + dy[k][j]이다.
  • i도시에서 i도시로 즉, 자기 자신에게 가는 경우는 0이다.

🚀 나의 풀이 ⭕


import sys 
sys.stdin=open('input.txt', 'r')

if __name__=="__main__":
    n,m = map(int, input().split())
    dy=[[5000]*(n+1) for _ in range(n+1)]
    for i in range(1,n+1):
        dy[i][i]=0
    for i in range(m):
        a,b,c=map(int, input().split())
        dy[a][b]=c              # a도시에서 b도시로 가는데 필요한 비용 c
# ----------- 여기까지 입력 ---------------------
# --------- 플로이드 와샬 알고리즘 --------- 
    for k in range(1,n+1):                      # 도시 1부터 n까지 k도시를 거친다고 할때 
        for i in range(1,n+1):
            for j in range(1,n+1):
                # i->j랑 i->k->j중 더 최단 비용인거 
                dy[i][j] = min(dy[i][j], dy[i][k]+dy[k][j])
# ----------- 여기부터 출력 ---------------------
    for i in range(1, n+1):
        for j in range(1, n+1):
            if dy[i][j]==5000:          # 변한게 없으면 
                print('M', end=' ')
            else:
                print(dy[i][j], end=' ')
        print()

2. 회장뽑기 (플로이드-워샬 응용)

월드컵축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이모임은 만들어진지 얼마 되지 않았기 때문에 회원사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 서로 모두 알 수 있 다.
각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.
예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다.
어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나, 친구의 친구임을 말한다.
또한, 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친국의 친구의 친구임을 말한다.
4점, 5점등은 같은 방법으로 정해진다.
각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구 사이이면서 동시에 친구의 친구 사이이면, 이 두 사람은 친구사이라고 본다. 회장은 회원들 중에서 점수가 가장 작은 사람이 된다.
회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

▣ 입력설명

입력의 첫째 줄에는 회원의 수가 있다.
단, 회원의 수는 50명을 넘지 않는다.
둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 회원의 수만큼 번호가 붙어있다.
마지막 줄에는 -1이 두 개 들어있다.

▣ 출력설명

첫째 줄은 회장 후보의 점수와 회장후보 수를 출력하고 두 번째 줄은 회장 후보를 모두 출력 한다.

▣ 입력예제 1

5

1 2

2 3
3 4
4 5
2 4
5 3
-1 -1

▣ 출력예제 1

2 3
2 3 4

설명

  • 표를 그리자
-12345
101223–> 1번회원은 3
210112–> 2번회원은 2
321011–> 3번회원은 2
421101–> 4번회원은 2
532110–> 5번회원은 3
  • 플로이드-와샬
  • i라는 사람의 친구 j 사이에 k라는 친구가 있을 수 있음을 고려하여 플로이드-와샬

🚀 나의 풀이 ⭕

import sys 
sys.stdin=open('input.txt', 'r')



if __name__=="__main__":
    n = int(input())            # 회원의 수 
    dy = [[100]*(n+1) for _ in range(n+1)]
    for i in range(1,n+1):
        dy[i][i]=0
    while True:
        a, b = map(int, input().split())
        if a == -1 and b == -1:
            break 
        else:
            dy[a][b]=1
            dy[b][a]=1
# ------------------ 여기까지 입력 받음 -------------------------
# ---- 플로이드-와샬 -----
    for k in range(1,n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                dy[i][j] = min(dy[i][j], dy[i][k]+dy[k][j])
# ---------- 출력 --------------------
    for m in range(1, n+1):
        print(dy[m][1:])

    res = [max(dy[m][1:]) for m in range(1, n+1)]   # 각 행별 최대값
    score = min(res)
    candidates = [i+1 for i in range(0, n) if res[i]== score]
    print("%d %d" %(score, len(candidates)))
    for x in candidates:
        print(x, end=' ')

3. 위상정렬 (그래프 정렬)

위상정렬은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 각각의 일의 선후관계가 복잡하게 얽혀있을 때 각각 일의 선후관계를 유지하면서 전체 일의 순서를 짜는 알고리즘입니다. 만약 아래와 같은 일의 순서를 각각 지키면서 전체 일의 순서를 정한다면
1 4 //1번일을 하고 난 후 4번일을 해야한다.
5 4
4 3
2 5
2 3
6 2

전체 일의 순서는 1, 6, 2, 5, 4, 3과 같이 정할 수 있다. 전체 일의 순서는 여러 가지가 있습 니다 그 중에 하나입니다.

▣ 입력설명

첫 번째 줄에 전체 일의 개수 N과 일의 순서 정보의 개수 M이 주어집니다. 두 번째 줄부터 M개의 정보가 주어집니다.

▣ 출력설명

전체 일의 순서를 출력합니다.

▣ 입력예제 1

6 6
1 4
5 4
4 3
2 5
2 3
6 2

▣ 출력예제 1

1 6 2 5 4 3

설명

  1. 이번에는 방향이 있다.
  2. 진입차수가 없는 노드는 최우선 순위이다.
  3. 진입차수를 증가시키며 큐에 넣고 빼자

노드끼리의 연결을 나타내는 2차원 배열 graph를 만들고
자기 노드로 부터 들어오는 진입차수를 나타내는 degree를 만든다.

진입차수를 증가시킨다. degree = | 0 | 1 | 2 | 3 | 4 | 5 | 6 |

degree[4]는 2이다. 이유: 4로 들어오는 방향이 2개임 (1 4), (5 4)

degree =0123456
 012210 

큐를 만든다. 0인것을 큐에 넣고 빼면서 그 수의 진입 원천의 수의 값을 감소시킨다.

🚀 나의 풀이 ⭕

import sys 
from collections import deque
sys.stdin=open('input.txt', 'r')

if __name__=="__main__":
    n,m=map(int, input().split())
    graph=[[0]*(n+1) for _ in range(n+1)]
    degree=[0]*(n+1)
    dQ=deque()

    for i in range(m):
        a,b = map(int, input().split())
        graph[a][b]=1                       # a노드에서 b노드로 
        degree[b]+=1                        # 진입된 노드 b의 진입차수를 센다. 
    
    for i in range(1, n+1):
        if degree[i]==0:            # 진입된 노선이 없으면 
            dQ.append(i)            # 최우선, 큐에 넣는다. 
    
    # 큐가 사라질때까지
    while dQ:
        x=dQ.popleft()
        print(x, end=' ')
        for i in range(1, n):
            if graph[x][i]==1:      # 큐에 뺀 x에서 i로 가는 진입수가 있다면 
                degree[i]-=1        # 값을 빼면서 진행하면서 
                if degree[i]==0:
                    dQ.append(i)


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

© 2020. All rights reserved.

따라쟁이