[SWEA 5644번] 무선충전 :: 늦깎이 IT

[SWEA 5644번] 무선충전 URL

1. 10 X 10 Map에 배터리의 해당 정보를 비트마스크를 이용하여 저장한다.

1) 0번 배터리 : (1 << 0) = 1

2) 1번 배터리 : (1 << 1) = 2

3) 2번 배터리 : (1 << 2) = 4

4) 3번 배터리 : (1 << 3) = 8

즉, Map[row][col]에 10이 저장되어 있다면, 10 = 2 + 8 이므로, 1번, 3번 배터리의 영향을 받는 지역이라고 할 수 있다.

2. 사람 A, B를 옮겨가면서 각 사람마다 해당 위치의 Map[row][col] 값을 확인한다. 비트마스킹 연산을 진행하면서

해당 위치가 어느 배터리의 영향을 받는지 확인하고, List에 배터리 번호를 저장한다.

3. 사람 A, B의 위치에서 영향을 받는 배터리의 정보를 List에 저장했다면 모든 경우의 수를 계산하며 최대값을

찾는다. 경우의 수는 크게 3가지로 나눌 수 있다.

1) A만 배터리 영향을 받을 경우

2) B만 배터리 영향을 받을 경우

3) A, B 모두 배터리 영향을 받을 경우

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Solution {
 
    public static int N, tCase, M, A, ans;
    public static int[][] move, map, persons;
    public static int[] ap;
    public static int[] dirX = new int[] { 0, -1, 0, 1, 0 };
    public static int[] dirY = new int[] { 0, 0, 1, 0, -1 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        N = 10;
        StringTokenizer st = new StringTokenizer(br.readLine());
        tCase = Integer.parseInt(st.nextToken());
 
        for (int t = 1; t <= tCase; t++) {
 
            st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            A = Integer.parseInt(st.nextToken());
 
            ans = 0;
            map = new int[N][N];
            move = new int[2][M];
            persons = new int[2][2];
            ap = new int[A];
 
            persons[0][0] = persons[0][1] = 0;
            persons[1][0] = persons[1][1] = 9;
 
            for (int i = 0; i < 2; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < M; j++) {
                    move[i][j] = Integer.parseInt(st.nextToken());
                }
            }
 
            for (int i = 0; i < A; i++) {
                st = new StringTokenizer(br.readLine());
                int col = Integer.parseInt(st.nextToken());
                int row = Integer.parseInt(st.nextToken());
                int area = Integer.parseInt(st.nextToken());
                int power = Integer.parseInt(st.nextToken());
                setBattery(row - 1, col - 1, i, area);
                ap[i] = power;
            }
            solve();
            for (int i = 0; i < M; i++) {
                persons[0][0] += dirX[move[0][i]];
                persons[0][1] += dirY[move[0][i]];
 
                persons[1][0] += dirX[move[1][i]];
                persons[1][1] += dirY[move[1][i]];
                solve();
            }
            System.out.println("#" + t + " " + ans);
        }
    }
 
    public static void solve() {
 
        List<List<Integer>> list = new ArrayList<>();
 
        for (int i = 0; i < 2; i++) {
 
            int row = persons[i][0];
            int col = persons[i][1];
            List<Integer> person = new ArrayList<>();
 
            if (map[row][col] > 0) {
 
                for (int j = 0; j < A; j++) {
 
                    if ((map[row][col] & (1 << j)) > 0) {
                        person.add(j);
                    }
                }
            }
            list.add(person);
        }
 
        List<Integer> a = list.get(0);
        List<Integer> b = list.get(1);
 
        int maxVal = 0;
        if (a.size() == 0 && b.size() > 0) {
 
            for (int i = 0; i < b.size(); i++)
                maxVal = Math.max(maxVal, ap[b.get(i)]);
 
        } else if (a.size() > 0 && b.size() == 0) {
 
            for (int i = 0; i < a.size(); i++)
                maxVal = Math.max(maxVal, ap[a.get(i)]);
 
        } else if (a.size() > 0 && b.size() > 0) {
            for (int i = 0; i < a.size(); i++) {
 
                for (int j = 0; j < b.size(); j++) {
 
                    int sum = ap[a.get(i)];
                    if (a.get(i) != b.get(j)) {
                        sum += ap[b.get(j)];
                    }
 
                    maxVal = Math.max(maxVal, sum);
                }
            }
        }
        ans += maxVal;
 
    }
 
    public static void setBattery(int startRow, int startCol, int batNum, int area) {
 
        boolean[][] visited = new boolean[N][N];
        batNum = (1 << batNum);
 
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(startRow, startCol, 0));
 
        visited[startRow][startCol] = true;
        map[startRow][startCol] += batNum;
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int row = node.row;
            int col = node.col;
            int cnt = node.cnt;
 
            if (cnt >= area)
                continue;
 
            for (int i = 1; i <= 4; i++) {
 
                int nr = row + dirX[i];
                int nc = col + dirY[i];
 
                if (isBoundary(nr, nc) && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    map[nr][nc] += batNum;
                    q.offer(new Node(nr, nc, cnt + 1));
                }
            }
 
        }
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < N);
    }
 
    public static void showMap(int[][] map) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}
 
class Node {
 
    int row;
    int col;
    int cnt;
 
    public Node(int row, int col, int cnt) {
        this.row = row;
        this.col = col;
        this.cnt = cnt;
    }
 
}