[이코테] part 2_6주차_플로이드 와샬

python/23년도 겨울 방학 코딩 스터디

[이코테] part 2_6주차_플로이드 와샬_p.261 미래 도시

소곡이 2023. 2. 15. 23:38

728x90

나왔사와여

문제(출처 : <이것이 코딩 테스트다> )

답안지

이번 주차에서는 최단 경로 알고리즘에 관해 배웠는데. 최단 경로부터 가물가물해서. 옛날에 하던 핸드 시뮬레이션을 했다. 그리고 답은 답안지를 베낀 것임. 제가 푼 것 XXXXX

# 값 초기화, 원래 코드는 입력 받는건데, 일일이 입력받기 귀찮아서 명시해줌
INF = int(1e9)

# n=회사(노드) 개수, m=회사끼리 연결된 도로(간선) 개수
n, m = 5, 7 
graph = [[INF]*(n+1) for _ in range(n+1)]

# 각 간선에 대한 정보를 입력받아 그 값으로 초기화
graph[1][2] = 1; graph[2][1] = 1;
graph[1][3] = 1; graph[3][1] = 1;
graph[1][4] = 1; graph[4][1] = 1;
graph[2][4] = 1; graph[4][2] = 1;
graph[3][4] = 1; graph[4][3] = 1;
graph[3][5] = 1; graph[5][3] = 1;
graph[4][5] = 1; graph[5][4] = 1;

# 방문판매 회사 X와 소개팅할 회사 K
x, k = 4, 5

# 자기 자신에게 가는 비용은 0으로 초기화
for a in range(1, n+1):
    for b in range(1, n+1):
        if a==b: graph[a][b]=0
        
# 플로이드 워셜
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])
        print(k, a,b,  graph)
                    
distance = graph[1][k]+graph[k][x] # 1= a회사, k = 소개팅 회사, x = 방문판매활 회사

# 못 가는 경우 -1 출력
if distance >= INF: print(-1)
else: print(distance)

분석

플로이드 와샬 메인 코드다.

1. 1부터 시작하는 이유는 노드 번호를 맞추기 위함이다. 노드가 1번부터 시작하니까...ㅇㅇㅇ

2. 4번 코드는 개인적인 생각으로 아래와 같다 (아닐 수도 있으니까 흘려들을 것)

graph[a][b] : a노드에서 b노드로 가는 가중치
graph[a][k] + graph[k][b] : a노드에서 k노드에 갔다가 k노드에서 b로 가는 가중치 합

예를 들어서 아래 그래프에서 5에서 3을 가고 싶다고 가정하자. (노드가 3개, 간선이 3개다. 나머지 지저분한 선은 무시함)

그럼 2가지 방법이 있다.

1. 5노드에서 3번 노드로 한 번에 가기. 이런 경우 가중치는 10이다.

2. 5노드에서 4번 노드에 갔다가, 4번 노드에서 3번 노드로 가기. 이런 경우 가중치는 7이다.

그렇다면 최단 경로 문제에서는 가장 가중치 값이 적은 방향을 선택하기 때문에 2번을 선택하게 된다.

보통은(?) 간선마다의 가중치 값이 다른데, 이 문제에서는 1로 통일해서 좀 헷갈릴 수 있을 것 같다.

가쟈

% 주의 아래부터는 소곡이가 이거 공부할 때 쓴 방법임%

일단 이런 그래프가 있고 1번에서 4번으로 가는 최단 경로를 알고 싶다고 하자.

값 초기화

그래프는 아래와 같이 그릴 수 있다.

플로이드 와샬은 모든 노드에서 모든 노드로의 최단 경로를 그리다보니 이렇게 2차원 배열로 그린다. 머리아프게 왜 2차원 배열을 쓰지...? 싶겠지만.

나는 간단하게 행이 현재 노드이고 열이 방문할 노드라고 생각하고 있다.

2차원 배열은 아래와 같이 채운다.

자기 자신은 가중치가 0이다. ex) (1,1), (2,2), (3,3), (4,4)
대각선을 제외한 곳은 모두 INF(무한)으로 채운다.
그리고 간선의 가중치를 넣어준다. 양방향이기 때문에 행과 열의 숫자를 바꿔서도 입력해준다. ex) (1,2)->(2,1)의 간선의 가중치가 2 이므로 둘 다 2를 넣어준다.