[BOJ] 1058 친구 - JAVA

1. 문제

1058번: 친구

지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.
A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.

첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.

첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다.

---

2. 풀이

입력

Y면 true, 아니라면 false를 저장한다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
boolean[][] map = new boolean[N][N];

String line;
for(int i=0;i<N;i++){
   line = in.readLine();
   for(int j=0;j<N;j++){
      map[i][j] = line.charAt(j)=='Y';
   }
}

 

탐색

1.  플로이드 워샬 알고리즘을 활용했다. 위의 map에는 처음 상태(직접친구), res에는 간접친구를 저장한다.

2.  i==k, i==j, j==k인 경우, res[i][j]가 이미 true인 경우, map[i][j]가 true인 경우를 거른다.

3.  map[i][k]가 true고 map[k][j]가 true인 경우 k를 매개체로 i와 j가 연결된다. res[i][j]에 true를 저장한다.

boolean[][] res = new boolean[N][N];
for(int k=0;k<N;k++){
   for(int i=0;i<N;i++){
      if(i==k) continue;
      for(int j=0;j<N;j++){
         if(i==j || j==k || res[i][j] || map[i][j]) continue;
         if(map[i][k]&&map[k][j]) res[i][j] = true;
      }
   }
}

 

출력

res[i][j]가 true이거나 map[i][j]가 true인 경우 카운팅한다.

가장 큰 값을 출력한다.

int tmp, answer=0;
for(int i=0;i<N;i++){
   tmp = 0;
   for(int j=0;j<N;j++){
      if(res[i][j] || map[i][j]) tmp++;
   }
   if(answer<tmp) answer = tmp;
}

System.out.println(answer);

---

3. 결과

if(i==j || j==k || res[i][j] || map[i][j])에서 res[i][j]를 빠뜨려서 총 친구가 2명인 경우를 제대로 탐색하지 못했다.