[JAVA]백준 1058번: 친구

 

www.acmicpc.net/problem/1058

1058번: 친구

 

1. 문제 설명

 

가장 2-친구의 수가 많은 사람의 2-친구수를 구한다.

2-친구란 두 사람이 친구이거나, A와 친구이고 B와 친구인 친구 C가 존재할 경우 A와 B는 2-친구라고 한다.

 

첫 번째 코드는 플로이드 와샬 알고리즘을 사용했다.

O(n^3)의 시간 복잡도를 가지며 모든 꼭짓점 사이의 최단 경로를 구하는 알고리즘이다.

 

두 번째 코드는 플로이드 와샬 알고리즘에 대한 지식 없이 처음 문제를 풀었을 때 짠 코드이다.

O(n^3)의 복잡도를 가지며 A와 B가 친구일 경우 친구의 수를 증가시키고, A와 C가 친구가 아닐 경우, A와 친구이며 C와 친구인 B를 찾으면서 B가 있을 경우에 친구의 수를 증가시킨다.

 

두번째두 번째 코드도 올리긴 했지만 두 번째 코드보다는 플로이드 와샬 알고리즘으로 푸는 게 더 좋을 듯하다.

 

 

 

2. 코드

 

 

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static String[] friend_list=new String[51];
    public static int friend_num;
    public static int[][] floyd=new int[51][51];

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);

        friend_num=scan.nextInt();

        for(int x=0;x<friend_num;x++){
            friend_list[x]=scan.next();
        }

        System.out.println(floyd_base_list());


        scan.close();
    }

    public static int floyd_base_list(){

        for(int x=0;x<friend_num;x++){
            for(int y=0;y<friend_num;y++){

                // 자기 자신과의 거리는 9999로 설정한다.
                if(x==y){
                    floyd[x][y]=9999;
                    continue;
                }

                char temp=friend_list[x].charAt(y);

                // 둘이 친구일 경우 거리는 1, 아닐 경우 9999로 설정한다.
                if(temp=='Y')
                    floyd[x][y]=1;
                else
                    floyd[x][y]=9999;
            }
        }

        floyd_make();

        int max=floyd_num();

        return max;
    }

    public static void floyd_make(){

        // x: 기준 정점
        // y: 시작
        // z: 도착
        // y->z로 가는 경로보다 x->y->z로 가는 경로가 짧으면 값을 수정한다.
        for(int x=0;x<friend_num;x++){
            for(int y=0;y<friend_num;y++){
                for(int z=0;z<friend_num;z++){
                    if(x==y || z==x || z==y)
                        continue;

                    if(floyd[y][z]>floyd[y][x]+floyd[x][z])
                        floyd[y][z]=floyd[y][x]+floyd[x][z];
                }
            }
        }
    }

    public static int floyd_num(){
        int max=0;

        for(int x=0;x<friend_num;x++)
        {

            int sum=0;

            // 2-친구의 수를 구한다.
            for(int y=0;y<friend_num;y++){
                if(floyd[x][y]<=2)
                    sum++;
            }

            if(max<sum)
                max=sum;
        }

        return max;
    }





}

 

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static String[] friend_list=new String[51];
    public static int friend_num;

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);

        friend_num=scan.nextInt();

        for(int x=0;x<friend_num;x++){
            friend_list[x]=scan.next();
        }

        System.out.println(find_friend_num());


        scan.close();
    }

    public static int find_friend_num(){

        int max=0;

        for(int x=0;x<friend_num;x++){

            int sum=0;

            for(int y=0;y<friend_num;y++){

                if(x==y)
                    continue;

                char temp=friend_list[x].charAt(y);

                if(temp=='Y')
                    sum++;
                else if(find_two_friend(x,y))
                    sum++;
            }

            if(max<sum)
                max=sum;
        }

        return max;
    }

    public static boolean find_two_friend(int base_index,int find_index){
        for(int x=0;x<friend_num;x++){
            char temp_find=friend_list[x].charAt(find_index);

            if(temp_find=='Y'){
                char temp_base=friend_list[base_index].charAt(x);

                if(temp_base=='Y')
                    return true;
            }
        }

        return false;
    }





}