1058_친구

사용 알고리즘: 플로이드 워셜

사용 언어: java

 

import java.io.*;
import java.util.*;

public class Main_1058_friend {
    static int inssa = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] graph2 = new char[n][n];
        int[][] graph = new int[n][n];

        for(int i=0; i<n; i++) {
            String str = sc.next();
            for(int j=0; j<n; j++) {
                graph2[i][j] = str.charAt(j);
            }
        }// 입력

        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                for(int k=0; k<n; k++) {
                    if(i!=j && (graph2[i][j]=='Y' || graph2[i][k]=='Y' && graph2[k][j]=='Y')){
                        graph[i][j] = 1;
                        graph[j][i] = 1;
                    }
                }
            }
        }

        for(int i=0; i<n; i++) {
            int sum=0;
            for(int j=0; j<n; j++) {
                if(graph[i][j]!=0) sum++;
            }
            inssa = Math.max(inssa, sum);
        }

        System.out.println(inssa);

    }
}

 

 

발생한 문제:

1. IDE 없이 코딩하는 연습을 하다가, 에러난 걸 잡기 힘들었음 (sc.next()로 받지 않고 sc.nextLine()으로 받았었는데, 여기서 indexoutofbound에러가 났음. 아무래도 엔터까지 받..나..?)

 

2. 처음엔 char[][] graph2 배열을 따로 만들지 않고 그냥 int[][] graph에 Y는 1로 받은 후 + 다리 건너 친구는 2로 표시해서 그 수를 세었는데... 잘못 나오는 테케가 있었음.

이유? -> 원래 1-친구인데 어떤 경로를 통해 2-친구가 될 수 있는 사이가 먼저 발견되어 그 자리가 2로 치환되어 실제 2-친구인 관계가 3-이상 친구로 판단되는 경우가 발생하는 거 같음.