BOJ) 사회망 서비스(SNS) (2533 번)

사회망 서비스(SNS)

2533번: 사회망 서비스(SNS)

 

효율적인 풀이 방법이 떠오르지 않아, 다른 분들이 푼 방법을 보고 이해했다.

 

먼저, 처음 생각했던 방식은 아래 코드의 로직과 크게 다르지는 않지만, 효율적이지는 않다.

모든 점에서 시작해서, 본인이 얼리어답터일 경우, 몇명의 얼리어답터가 존재해야 문제의 조건을 만족시키는지 구하는 것이었다.

 

하지만, 메모이제이션을 하면 효율적으로 풀 수 있을 것 같아서, 이와 관련해서 생각하다가 실패했다.

그래서 다른 분들의 풀이를 보니까 이해가 됐다.

자신이 얼리 어답터면 친구들이 얼리 어답터이든 레이트 어답터이든 상관 없이 내 친구들을 교화할 수 있고, 내 친구들이 교화하는 친구들의 수까지 저장해주면 된다.

반면, 레이트 어답터면 친구들이 얼리어답터여야 문제의 조건이 성립하게 된다.

이를 DFS 및 DP를 이용해서 구현하는 로직이었다.

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class SNS_2533 {
  static final int LENGTH =2, EARLY_ADAPTOR =1, LATE_ADAPTOR =0; // dp의 길이, 얼리 어답터 인덱스, 레이트 어답터 인덱스
  static int[][] dp; // 자신이 얼리 어답터일 때와 레이트 어답터일 때의 값을 저장
  static boolean[] visit; // 방문 체크
  static List<Integer>[] graph; // 연결 그래프

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    init(n); // init graph, dp, visit

    for(int i=1; i<n; i++) { // set graph
      StringTokenizer st = new StringTokenizer(br.readLine());
      int left = Integer.parseInt(st.nextToken()), right = Integer.parseInt(st.nextToken());
      graph[left].add(right);
      graph[right].add(left);
    }

    br.close();
    solution();
  }

  private static void init(int n) {
    graph = new ArrayList[n+1];
    for(int i=1; i<=n; i++) {
      graph[i] = new ArrayList<>();
    }
    dp = new int[n+1][LENGTH];
    visit = new boolean[n+1];
  }

  private static void solution() {
    final int STARTING_INDEX =1;
    find(STARTING_INDEX);
    System.out.println(Math.min(dp[STARTING_INDEX][EARLY_ADAPTOR], dp[STARTING_INDEX][LATE_ADAPTOR]));
  }

  private static void find(int idx) {
    visit[idx] = true;
    dp[idx][LATE_ADAPTOR] = LATE_ADAPTOR;
    dp[idx][EARLY_ADAPTOR] = EARLY_ADAPTOR;
    for(int next : graph[idx]) {
      if(visit[next]) {
        continue;
      }
      find(next);
      dp[idx][LATE_ADAPTOR] += dp[next][EARLY_ADAPTOR]; // 자신이 레이트 어답터면, 친구들 모두 얼리 어답터.
      dp[idx][EARLY_ADAPTOR] += Math.min(dp[next][LATE_ADAPTOR], dp[next][EARLY_ADAPTOR]); // 자신이 얼리 어답터면 뭐든 OK
    }
  }
}

 

참고

https://comyoung.tistory.com/41