[PS | 한 번에 맞자!] 백준 1507

0. 문제 설명

궁금한 민호

1507번: 궁금한 민호

---

1. 문제 생각

플로이드 워셜의 응용으로, 플로이드 워셜의 완성본을 보고, 어떤 간선들이 실질적으로 쓰이는지에 대해 추적하는 문제이다. 따라서 그림에서 보이는 것처럼 직접적으로 가는 길의 가중치만을 표현하기 위해 '플로이드 워셜을 이용하여 건너 가는 것들'에 대한 값들은 0으로 바꾸어주면 된다. 

'-1'을 출력하는 것은 플로이드와샬로 더 짧은 거리로 갈 수 있는 거리가 있는데 '완성본'에서 그 짧은 거리가 반영되어 있지 않았을 때 출력해주면 된다.

---

2. 문제 구현

import copy

N=int(input())
List=[]
for _ in range(N):
    List.append(list(map(int,input().split())))

newList=copy.deepcopy(List)

flag=True
for k in range(N):
    for i in range(N):
        for j in range(N):
            if i==j or j==k or i==k: continue
            if List[i][k]+List[k][j]==List[i][j]:
            # print(i,j,k)
                newList[i][j]=0; newList[j][i]=0
            elif List[i][k]+List[k][j]<List[i][j]:
                flag=False
ans=0
# print(newList)
for i in range(N):
    ans+=sum(newList[i])

if flag:
    print(ans//2)
else:
    print(-1)

 

---

3. 한 번에 풀었는가? X

python copy와 deepcopy의 차이를 이해하지 못해 한 번 틀렸다. 결론적으로는 a라는 list를 독립적인 list로 복사하기 위해서는 copy 모듈의 deepcopy 함수를 사용해야 한다.

import copy

# 원본 리스트와 내부 리스트 생성
original_list = [1, 2, 3, [4, 5]]

# 얕은 복사 (shallow copy)
shallow_copied_list = copy.copy(original_list)

# 깊은 복사 (deep copy)
deep_copied_list = copy.deepcopy(original_list)

# 원본 리스트의 내부 리스트를 변경
original_list[3][0] = 99

# 결과 출력
print("Original List:", original_list)
print("Shallow Copied List:", shallow_copied_list)
print("Deep Copied List:", deep_copied_list)

'''
Original List: [1, 2, 3, [99, 5]]
Shallow Copied List: [1, 2, 3, [99, 5]]
Deep Copied List: [1, 2, 3, [4, 5]]
'''