반응형 그래프2 [Python] 백준 1325: 효율적인 해킹 실버1~2 문제를 손풀기 겸 뇌 깨우기로 계속해서 풀고 있다. 한창 백준 티어 끌어올리기 할 때 만큼 빠르지는 않지만 문제 해석 능력과 자료구조, 알고리즘 적용 감각이 돌아오고 있는 것이 느껴저 좋다. 이번 문제는 간단하게 그래프를 사용하여 풀 수 있는 문제이다. 문제 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다. 이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다. 이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹.. 2024. 4. 7. [코드조각] 플로이드-워셜 플로이드-워셜 알고리즘은 그래프 간의 모든 정점에서 다른 정점까지의 최단거리를 쉽게 구하는 알고리즘이다. 모든 정점과 정점 사이의 최단거리가 필요하거나, 키 비교, 줄 세우기 등의 문제에서 사용할 수 있다. import math N = int(input()) #정점의 개수 M = int(input()) #입력할 간선 정보의 개수 #정점과 정점사이의 거리. d[i][j]는 노드 i에서 노드 j까지의 거리 d = [[math.inf for i in range(N)] for j in range(N)] #자기 자신부터 자기 자신의 거리가 0 for i in range(N): d[i][i] = 0 #간선 정보 입력 while M: # 출발지점, 끝지점, 비용 S, E, C = map(int, input().spl.. 2021. 6. 11. 이전 1 다음 반응형