[Platinum V] XOR 그룹 - 14258

문제 링크

성능 요약

메모리: 56844 KB, 시간: 1544 ms

분류

자료 구조, 분리 집합, 오프라인 쿼리

제출 일자

2025년 2월 19일 16:39:34

문제 설명

N*M 격자에 서로 다른 수가 하나씩 들어가 있다. XOR 그룹이라는 것을 정의를 하여 합을 최대로 하려한다. XOR 그룹이란 위, 아래, 오른쪽, 왼쪽으로 인접한 칸에 수가 있다면, 그 칸과 연결되어 그 수를 모두 XOR한 값을 가지는 그룹이 된다. 만약, 중간에 수가 빠져있으면, 연결이 되지 않으므로, 한 격자판에 여러 XOR 그룹이 있을 수 있다.

이제 격자판에서 작은 수부터 제거해 나갈 것이다. 하나를 지울 때 마다 XOR 그룹이 변하는데, XOR그룹의 값의 합의 최대가 될 때, 그 값을 구하여라.

입력

첫째 줄에 n, m이 주어진다.(1 ≤ n, m ≤ 1,000)

다음 n줄에는 격자의 i번째 줄의 수 m개가 주어진다. 수는 1,000,000보다 크지 않은 음이 아닌 정수이다.

출력

XOR 그룹의 값의 합이 최대가 되는 값을 구하여라

문제 풀이

제일 작은수를 제거해나가는 대신 빈 칸에서 제일 큰수를 넣어가며 진행했다. 이때 그룹을 이루는 것끼리 union-find로 진행할 수 있다.

코드

코드 1

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    class Cell implements Comparable<Cell> {
        int r, c, val;
        public Cell(int r, int c, int val) {
            this.r = r;
            this.c = c;
            this.val = val;
        }

        @Override
        public int compareTo(Cell o) {
            return o.val - this.val;
        }
    }
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, M;
    static long res;
    static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, 1, -1};
    static int[] parent; // parent[i] = i값의 대표
    static long[] XOR; // XOR[px] = 대표px그룹의 XOR값
    static int[][] board;
    static boolean[][] visited;
    static Cell[] cells;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_14258_XOR그룹/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new int[N][M];
        visited = new boolean[N][M];

        parent = new int[1000001];
        XOR = new long[1000001];
        for(int i=0; i< parent.length; i++){
            parent[i] = i;
        }

        cells = new Cell[N*M];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                cells[i*M + j] = new Cell(i, j, board[i][j]);
            }
        }
        Arrays.sort(cells);

        long sum = 0;
        for(Cell c : cells) {
            int currR = c.r, currC = c.c;
            int currVal = c.val;

            visited[currR][currC] = true;
            XOR[currVal] = currVal;
            sum += currVal;

            for(int k=0; k<4; k++) {
                int nextR = currR + dr[k];
                int nextC = currC + dc[k];
                if(nextR >= 0 && nextR < N && nextC >= 0 && nextC < M && visited[nextR][nextC]) {
                    int nextVal = board[nextR][nextC];

                    int px = find(currVal);
                    int py = find(nextVal);

                    // 부모가 다르면 병합해야함
                    if(px != py){
                        sum -= XOR[px];
                        sum -= XOR[py];

                        union(currVal, nextVal);

                        sum += XOR[find(currVal)];
                    }
                }
            }
            res = Math.max(sum, res);
        }
        System.out.println(res);
        bw.flush();
        bw.close();
        br.close();
    }

    public int find(int x){
        if(parent[x] != x) return parent[x] = find(parent[x]);
        return parent[x];
    }

    public void union(int x, int y){
        int px = find(x);
        int py = find(y);
        if(px == py) return;

        if(px < py){
            parent[py] = px;
            XOR[px] ^= XOR[py];
        }
        else{
            parent[px] = py;
            XOR[py] ^= XOR[px];
        }
    }
}

---

코드 2 (빠른 입출력)

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    class Cell implements Comparable<Cell> {
        int r, c, val;
        public Cell(int r, int c, int val) {
            this.r = r;
            this.c = c;
            this.val = val;
        }

        @Override
        public int compareTo(Cell o) {
            return o.val - this.val;
        }
    }
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, M;
    static long res;
    static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, 1, -1};
    static int[] parent; // parent[i] = i값의 대표
    static long[] XOR; // XOR[px] = 대표px그룹의 XOR값
    static int[][] board;
    static boolean[][] visited;
    static Cell[] cells;
    static FastReader fr;
    public class FastReader {
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[16384];
            bufferPointer = bytesRead = 0;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, buffer.length);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            return neg ? -ret : ret;
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        fr = new FastReader();
        N = fr.nextInt();
        M = fr.nextInt();
        board = new int[N][M];
        visited = new boolean[N][M];

        parent = new int[1000001];
        XOR = new long[1000001];
        for(int i=0; i< parent.length; i++){
            parent[i] = i;
        }

        cells = new Cell[N*M];
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                board[i][j] = fr.nextInt();
                cells[i*M + j] = new Cell(i, j, board[i][j]);
            }
        }
        Arrays.sort(cells);

        long sum = 0;
        for(Cell c : cells) {
            int currR = c.r, currC = c.c;
            int currVal = c.val;

            visited[currR][currC] = true;
            XOR[currVal] = currVal;
            sum += currVal;

            for(int k=0; k<4; k++) {
                int nextR = currR + dr[k];
                int nextC = currC + dc[k];
                if(nextR >= 0 && nextR < N && nextC >= 0 && nextC < M && visited[nextR][nextC]) {
                    int nextVal = board[nextR][nextC];

                    int px = find(currVal);
                    int py = find(nextVal);

                    // 부모가 다르면 병합해야함
                    if(px != py){
                        sum -= XOR[px];
                        sum -= XOR[py];

                        union(currVal, nextVal);

                        sum += XOR[find(currVal)];
                    }
                }
            }
            res = Math.max(sum, res);
        }
        System.out.println(res);
    }

    public int find(int x){
        if(parent[x] != x) return parent[x] = find(parent[x]);
        return parent[x];
    }

    public void union(int x, int y){
        int px = find(x);
        int py = find(y);
        if(px == py) return;

        if(px < py){
            parent[py] = px;
            XOR[px] ^= XOR[py];
        }
        else{
            parent[px] = py;
            XOR[py] ^= XOR[px];
        }
    }
}