독립 도시

Last update: a year ago by nowwaterReading time: 2 min

문제

실전 유형 코딩 테스트 모의고사 3000 Part2. 2번 독립 도시

코드

코드 보기

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int v = sc.nextInt();
                if(v == 1 || i == j) arr[i] |= (1 << j);
            }
        }
        int ans = 0;
        for (int i = (1 << n) - 1; i > 0; --i) {
            int temp = i;
            for (int j = 0; j < n; j++)
                if((i & (1 << j)) > 0)
                    temp = temp & arr[j];
            if(temp == i){
                ans = Math.max(ans, check(temp, n));
            }
        }
        System.out.println(ans);
    }
    private static int check(int temp, int n) {
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if((temp & (1<<i)) > 0) ret += 1;
        }
        return ret;
    }
}

⭐️느낀점⭐️

그래프와 비트마스킹을 섞으니 혼잡스러웠다. 그래도 이해를 했으니 다음에 비슷한 문제에 적용하면 도움이 많이 될 것 같다.

풀이 📣

1️⃣ 그래프를 표현하기 위해 인접 행렬대신에 각 노드에 연결된 노드들을 비트마스킹을 위한 정수로 저장한다.

2️⃣ 모든 노드를 가지고 있는 상태값 (temp = (1 << n) - 1) 부터 차례로 탐색하면서, 만약 상태값이 j 번째 노드를 갖고 있다면 (((1 << j) & temp) > 0) 상태값과 j번째 노드의 인접한 노드들의 비트마스킹을 AND 연산한다.

3️⃣ 상태값이 가지고 있는 모든 노드들과 상태값을 AND 한 값이 처음의 상태값과 동일하다면, 상태값에 포함된 노드들이 모두 서로에 대해 인접하고 있음을 뜻한다.

4️⃣ 인덱스가 더 빠른 값이 더 앞에 놓여있음을 의미하기 때문에 가장 앞의 다른 색을 지워준다. 해당 값은 이전에 저장되어 있던 값과 우선순위를 맞춰주기 위해 원래 큐에 다시 삽입해주기 전에 n만큼 더한 인덱스 값으로 큐에 넣어준다. 이것이 우리가 찾고 있는 문제의 조건이다.

5️⃣ 이러한 상황을 클리크 라고 하는데, 문제의 조건이 최대 클리크를 찾는 것이므로, 모든 상태값에 대해 반복문을 돌면서 가장 큰 클리크 값을 찾아서 출력해주면 된다.

실수 😅

코드보기

// 54/60 점 받은 코드
import java.io.*;
import java.util.*;
class Main {
    static int n, arr[][];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
            {
                if(arr[i][j] == 1 && arr[j][i] == 1) {
                    int visited = 0;
                    visited |= (1 << i);
                    visited |= (1 << j);
                    ans = Math.max(ans, solution(visited));
                }
            }
        System.out.println(ans);
    }
    private static int solution(int visited) {
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if(((1 << i) & visited) > 0){
                for (int next = 0; next < n; next++) {
                    // 이미 포함된 경우는 탐색 x
                    if(((1 << next) & visited) > 0) continue;
                    if(arr[i][next] > 0 && isGroup(next, visited)){
                        ret = Math.max(ret, solution(visited | (1 << next)));
                    }
                }
            }
        }
        if(ret == 0) {
            for (int i = 0; i < n; i++) {
                if(((1 << i) & visited) > 0)
                    ret += 1;
            }
        }
        return ret;
    }
    private static boolean isGroup(int j, int visited) {
        for (int i = 0; i < n; i++) {
            if(((1 << i) & visited) > 0){
                if(arr[j][i] == 0 || arr[i][j] == 0) return false;
            }
        }
        return true;
    }
}

DFS 를 통해 i 노드와 j 노드가 서로 연결이 되어 있다면 visited에 추가하고, 현재까지 추가되지 않은 노드 중 추가된 노드들과 서로 다 연결될 수 있는 노드만 계속해서 visited 에 추가해나가는 방법을 썼다.

하지만 어떤 케이스에서 틀렸는지 잘 모르겠다..

👩‍💻 Problem Solving — Previous

GOORM

Next — 👩‍💻 Problem Solving

비상 연락망