반응형
12-24 07:02
- Today
- Total
Link
개발하는 고라니
[백준] 1058번 : 친구 본문
반응형
[플로이드 - 와샬, Floyd - Warshall]
A, B, C, D, E가 있다고 하자. A와 B가 친구이고, B와 C가 친구일 때 A와 C는 친구이다. 그럼 C와 D가 친구일 때 A와 D는 친구일까? 아니다. 2-친구이므로 나의 친구의 친구까지만 친구로 인정된다. 따라서 D는 A의 3-친구이다. 이 문제에서는 2-친구만을 답으로 원하므로 플로이드 와샬을 수행하여 각 친구들이 n-친구인지 구하고 2 이하인 친구들의 개수를 구하도록 한다. (0일 때는 친구가 아니므로 pass, 1와 2일 때만 카운트를 증가한다.)
# Code </>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static final int INF = 100000000;
static int[][] cost = new int[51][51];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
for(int i=1; i<=n; i++){
char[] str = br.readLine().toCharArray();
for(int j=1; j<=n; j++) {
if(i == j) continue;
cost[i][j] = str[j-1] == 'Y'? 1 : INF;
}
}
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
if (i == j) continue;
cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
}
int max = 0;
for(int i=1; i<=n; i++) {
int cnt = 0;
for (int j = 1; j <= n; j++)
if (cost[i][j] == 2 || cost[i][j] == 1) cnt++;
max = Math.max(max, cnt);
}
System.out.println(max);
}
}
반응형
'Programming > 백준' 카테고리의 다른 글
[백준] 2512번 : 예산 (0) | 2021.03.14 |
---|---|
[백준] 2617번 : 구슬 찾기 (0) | 2021.03.14 |
[백준] 9019번 : DSLR (0) | 2021.03.13 |
[백준] 10816번 : 숫자 카드 2 (0) | 2021.03.13 |
[백준] 1654번 : 랜선 자르기 (0) | 2021.03.13 |
Comments