[Java] 백준 1058 친구 - 실버2

https://www.acmicpc.net/problem/1058

1058번: 친구

 

 

bfs를 사용한 풀이(내 풀이)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

//[baekjoon] java-1058

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());
    ArrayList<Integer>[] arr = new ArrayList[cnt];
    for (int i =0; i<cnt; i++)
      arr[i] = new ArrayList<Integer>();

    for (int i =0; i<cnt; i++) {
      String s = br.readLine();

      for (int j =0; j<s.length(); j++) {
        if (s.charAt(j) == 'Y') {
          arr[i].add(j);
          arr[j].add(i);
        }
      }
    }

    int max = 0;
    for (int i =0; i<cnt; i++) {
      int[] visit = new int[cnt];
      visit[i] = 1;
      int result = 0;

      Queue<Integer> queue = new LinkedList<>();
      queue.add(i);

      while (!queue.isEmpty()) {
        int poll = queue.poll();
        if (visit[poll] > 2)
          break;

        for (Integer k: arr[poll]) {
          if (visit[k] == 0) {
            visit[k] = visit[poll] + 1;
            result++;
            queue.add(k);
          }
        }
      }

      if (result > max)
        max = result;
    }

    System.out.println(max);
  }
}

1. 입력을 ArrayList의 배열에 저장한다(그래프 저장하듯이)
2. 모든 경우에 대해 2-친구의 수를 계산한다
   
   • visit배열에 촌수+1의 값을 저장한다 
   • 만약 2-친구 이상이 되면 break 해줌 (bfs이기 때문에 촌수 111222333 이런식으로만 저장됨, 뒤에껀 볼 필요 없음)
3. 2-친구의 수가 max인 경우를 찾아 출력해줌

 

 

 

플루이드-워샬 알고리즘 풀이

• 모든 쌍 최단경로 길이를 구하여 2보다 작은(1-친구, 2-친구) 노드의 수를 계산하는 방법
• 풀이법 참고 블로그 https://blackvill.tistory.com/105

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());
    int[][] arr = new int[cnt][cnt];
    
    //초기화
    for (int i =0; i<cnt; i++) {
      for (int j =0; j<cnt; j++) {
        if (i==j)
          arr[i][j] = 0;
        else
          arr[i][j] = 60;
      }
    }

    //경로 입력받기
    for (int i =0; i<cnt; i++) {
      String s = br.readLine();

      for (int j =0; j<s.length(); j++) {
        if (s.charAt(j) == 'Y') {
          arr[i][j] = 1;
          arr[j][i] = 1;
        }
      }
    }

    //Floyd-Warshall
    for (int k =0; k<cnt; k++) {
      for (int i =0; i<cnt; i++) {
        if (i == k)
          continue;

        for (int j =0; j<cnt; j++) {
          if (j == k || j == i)
            continue;

          arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
        }
      }
    }

    //2-친구 수 계산
    int max = 0;
    for (int i =0; i<cnt; i++) {
      int friend2 = 0;
      for (int j=0; j<cnt; j++) {
        if (i == j)
          continue;

        if (arr[i][j] > 0 && arr[i][j] < 3)
          friend2++;
      }

      if (friend2 > max)
        max = friend2;
    }

    System.out.println(max);
  }
}

1. 노드 수만큼의 크기의 2차원 배열을 만들어주고, 무한대 값(60)으로 초기화해준다
   • 만약 i==j 이면 0으로 넣어줌
2. 입력값을 받아 배열에 다이렉트 경로값을 갱신해준다
3. Floyd-Warshall알고리즘으로 모든 쌍의 최단경로를 구한다
4. 모든 점에 대해 경로 길이가 1이나 2인 점의 개수를 카운트하고, max값을 갱신한다
5. max값을 출력

 

 

• 20ms정도 시간이 줄었고, 메모리는 500KB정도 줄었음
• bfs든 dp든 나쁘지 않은 풀이인듯