ayeongjin 님의 블로그

https://www.acmicpc.net/problem/1058 2-친구가 가장 많을떄, 그 2-친구 수를 출력하는 문제였다.(A와 B가 2-친구 되는 법 : A,B가 서로 친구이거나, 겹지인 C 존재) 그래서 브루트포스로 n번 사람의 2-친구 수를 전부 구해서 계산했다. # 성공 코드# 단순 그래프 탐색# python 32412 KB 48 msN = int(input())adjl = [input() for _ in range(N)]def friend(a, b): # 서로 친구인 경우 if adjl[a][b] == 'Y': return True # 겹지인이 존재할 경우 for f in range(N): if f == a or f == b: ..

🧐 플로이드-워셜 알고리즘: 모든 노드 간 최단 경로 찾기 1. 플로이드-워셜 알고리즘이란?플로이드-워셜(Floyd-Warshall) 알고리즘은 그래프의 모든 노드 쌍 간 최단 경로를 찾는 알고리즘입니다.동적 프로그래밍(Dynamic Programming) 기법을 사용하며, 다익스트라와 다르게 음수 가중치가 있는 그래프도 처리할 수 있다는 장점이 있습니다. 2. 알고리즘의 동작 원리이 알고리즘은 특정한 경유지 노드(k)를 거쳐 가는 경우와 바로 가는 경우를 비교하며 최단 경로를 갱신합니다.점화식:dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])dist[i][j]: 노드 i에서 노드 j로 가는 현재까지의 최단 거리k: 경유하는 노드 3. 알고리즘 구현INF ..