일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
Tags
- php 프로그래밍 입문 3판
- 배열
- php 프로그래밍
- 한정 분기
- 파이썬
- Flutter
- C
- 페이코 초대코드
- Java
- JAVA SPRING
- 스프링
- 자바
- 페이코 추천인코드
- php 프로그래밍 입문
- 플러터
- spring
- 자바 스프링
- programmers
- php 프로그래밍 입문 문제풀이
- 페이코 친구코드
- SWEA
- 플러터 개발환경 설정
- 페이코 추천인
- C언어
- php 프로그래밍 입문 예제
- php
- php 프로그래밍 입문 연습문제
- 최단 경로
- 백준
- php 프로그래밍 입문 솔루션
Archives
- Today
- Total
04-05 19:27
ImJay
[SWEA/Java] 1263. 사람 네트워크2 본문
반응형
[SWEA/Java] 1263. 사람 네트워크2
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
문제 해석
이 문제는 사회과학 연구에서 사용되는 네트워크 중요도 척도인 'Closeness Centrality' (CC)을 계산하는 문제이다. 네트워크 상의 모든 사용자 간 최단 경로의 합으로 정의된다. 각 사용자에 대해 다른 모든 사용자까지의 최단 경로를 더한 후, 가장 작은 값을 가진 사용자의 CC 값을 찾는 것이 목표다.
풀이 과정
이 문제의 풀이는 플로이드-와샬 알고리즘을 사용하여 모든 노드 쌍에 대한 최단 거리를 계산하는 것을 기본으로 한다. 주어진 인접 행렬에서 직접 연결되지 않은 노드 간의 거리는 매우 큰 값(1000)으로 초기 설정한다. 이후, 모든 노드 쌍에 대해 중간 노드를 거쳐 경로를 단축할 수 있는지 확인하며 행렬을 갱신한다. 모든 노드에 대해 계산된 최단 거리의 합을 구하고, 이 중 최소값을 결과로 반환한다.
코드
package edu.ssafy.im.SWEA.D6;
import java.io.*;
import java.util.StringTokenizer;
public class Solution {
private static int N;
private static int[][] graph;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
int TC = Integer.parseInt(br.readLine());
for (int T = 1; T <= TC; T++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
graph = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
graph[i][j] = Integer.parseInt(st.nextToken());
if (graph[i][j] == 0 && i != j) graph[i][j] = 1000; // 직접 연결되지 않은 노드 간 거리 설정
}
}
sb.append("#").append(T).append(" ").append(sol()).append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
}
private static int sol() {
// 플로이드-와샬 알고리즘을 사용한 모든 쌍 최단 경로 계산
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j) continue; // 자기 자신으로의 경로는 제외
graph[i][j] = Math.min(graph[i][k] + graph[k][j], graph[i][j]);
}
}
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
int sum = 0;
for (int j = 0; j < N; j++) {
sum += graph[i][j]; // 모든 노드까지의 거리 합 계산
}
ans = Math.min(ans, sum); // 최소 CC 값 찾기
}
return ans;
}
}
시간 복잡도 분석
플로이드-와샬 알고리즘의 시간 복잡도는 𝑂(𝑁3)이다. 여기서 𝑁은 최대 1000까지 가능하므로, 최악의 경우 알고리즘은 약 1,000,000,000번의 연산을 수행할 수 있다. 실제 시나리오에서는 입력 데이터의 크기와 테스트 케이스의 수에 따라 성능이 결정된다.
느낀점
네트워크 분석에 사용되는 중심성 지표를 계산하는 이 문제는 그래프 이론의 기본적인 알고리즘을 활용하는 좋은 실습이었다. 최단 경로 알고리즘의 여러 변형 중 하나인 플로이드-와샬 알고리즘의 이해도를 높일 수 있는 기회였다.
반응형
'SW Expert Academy' 카테고리의 다른 글
[SWEA/Java] 2112. 보호 필름 (0) | 2024.04.25 |
---|---|
[SWEA/Java] 5656. 벽돌 깨기 (0) | 2024.04.25 |
[SWEA/Java] 5658. 보물상자 비밀번호 (0) | 2024.04.19 |
[SWEA/Java] 5653. 줄기세포배양 (1) | 2024.04.19 |
[SWEA/Java] 5644. 무선 충전 (0) | 2024.04.18 |
Comments