[백준] 소셜 광고(java)

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

9335번: 소셜 광고

오랜만에 백준을 풀었는데 재미있는 문제가 있어서 가져왔다. 백트래킹을 통한 완전탐색 문제이다.

 

핵심

각각의 사람마다 광고를 보여줄지, 안 보여줄지 선택한다. 최대 인원은 20이다 -> 2^20 이므로 충분히 가능한 시간이다.

 

정답 코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static int n;
    private static int result;
    private static List<Integer>[] friendList;
    private static int[] visited;

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

        for (int i = 1; i <= test; i++) {
            result = Integer.MAX_VALUE;
            n = sc.nextInt();
            friendList = new ArrayList[n + 1];

            // 초기화
            for (int j = 1; j <= n; j++) {
                friendList[j] = new ArrayList<>();
            }
    
            // 친구 정보 넣기
            for (int j = 1; j <= n; j++) {
                int friendCount = sc.nextInt();

                for (int k = 0; k < friendCount; k++) {
                    int friend = sc.nextInt();
                    friendList[j].add(friend);
                }
            }

            visited = new int[n + 1];
            backTracking(0, 0);
            System.out.println(result);
        }
    }

    private static void backTracking(int index, int count) {
        if (count >= result) {
            return;
        }

        // 모든 사람들이 광고를 볼 수 있는지 확인
        if (index == n) {
            for (int i = 1; i <= n; i++) {
                if (visited[i] == 0) {
                    return;
                }
            }
            result = count;
            return;
        }
 
        // 선택
        visited[index + 1]++;
        for (int friend : friendList[index + 1]) {
            visited[friend]++;
        }
        backTracking(index + 1, count + 1);

        // 선택 해제
        visited[index + 1]--;
        for (int friend : friendList[index + 1]) {
            visited[friend]--;
        }
        backTracking(index + 1, count);
    }
}

해설

우선 friendList에 입력으로 들어오는 값을 순서대로 넣어준다.

주의할 점은 첫 시작 인덱스가 1이라는 점이다. (0은 아예 사용하지 않음)

이제 앞서 설명한 대로 각각의 사람에게 광고를 부여할지, 부여하지 않을지를 고른다.

만약 광고를 부여하면 해당 사람과 그의 친구들의 visited 카운트를 증가시킨다. 

이때 visited를 boolean이 아닌 int로 하는 이유는 이미 앞에서 선택했더라도 뒤에서 false를 줘버리면 초기화되기 때문이다.

이를 처음에 선택한 n값만큼만 탐색한다. 

n값과 일치하게 되었다면 현재 모든 사람이 광고를 볼 수 있는지 판단하고, 모든 사람이 볼 수 있다면 count를 result에 담는다.

바로 result에 담을 수 있는 이유는 이미 count가 result를 넘으면 return 하기에 최적의 정답임을 확신할 수 있기 때문이다.

 

배운 점

처음에 그리디로 접근해 보았다. 머리로는 완벽하다고 생각했는데, 계속해서 반례를 찾지 못하고 실패했다.

이후 완탕을 시도하였는데, 실수로 로직을 잘못 짜서 시간초과가 발생했다.

다시 처음부터 천천히 백트래킹으로 시도하니 정답을 맞힐 수 있었다.