[SWEA/Java] 5644. 무선 충전

[SWEA/Java] 5644. 무선 충전

SW Expert Academy

---

문제 해석

이 문제는 격자판 위에서 두 사용자가 주어진 경로를 따라 이동하며, 무선 충전기(AP)들로부터 최대한 많은 에너지를 충전하는 방법을 찾는 것이다. 각 충전기는 특정 범위와 충전 성능을 가지고 있으며, 사용자의 위치에 따라 충전 가능 여부가 결정된다. 사용자들은 각 시간 단위로 미리 정해진 방향으로 움직이며, 이동하는 동안 최적의 충전 방법을 통해 최대한 많은 에너지를 얻어야 한다.

풀이 과정

1. 입력 처리: 사용자의 이동 경로와 무선 충전기의 위치, 범위, 성능 정보를 입력받는다.
2. 초기 설정: 두 사용자의 초기 위치에서 시작하여, 각 시간 단위마다 충전기 범위 내에 들어가는지 확인하고 가능한 충전량을 계산한다.
3. AP 탐색: 각 사용자 위치별로 충전 가능한 AP를 식별한다.
4. 충전 계산: 두 사용자가 동일한 AP를 공유할 경우와 서로 다른 AP에서 충전할 경우를 분석하여 각 경우의 최대 충전량을 계산한다. 이때, 같은 AP를 사용하는 경우 충전 성능을 공유하므로, 충전량을 적절히 배분해야 한다.
5. 결과 도출: 각 시간 단위로 계산된 최대 충전량을 합산하여 최종적인 최대 충전량을 결과로 출력한다.

코드

package edu.ssafy.im.SWEA.D0.No5644;

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Solution {
    private final static int SIZE = 10; // 격자의 크기
    private final static int[][] direction = {{0, 0}, {-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 이동 방향 배열 (정지, 상, 우, 하, 좌)
    private int M; // 총 이동 시간
    private int[] a, b; // 사용자 A와 B의 이동 정보
    private AP[] ap; // AP 배열

    public static void main(String[] args) throws IOException {
        new Solution().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수
        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken()); // 총 이동 시간
            int A = Integer.parseInt(st.nextToken()); // AP의 수

            a = new int[M]; // 사용자 A의 이동 정보
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }

            b = new int[M]; // 사용자 B의 이동 정보
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                b[i] = Integer.parseInt(st.nextToken());
            }

            ap = new AP[A]; // AP 인스턴스 배열 생성
            for (int i = 0; i < A; i++) {
                st = new StringTokenizer(br.readLine());
                int y = Integer.parseInt(st.nextToken()) - 1;
                int x = Integer.parseInt(st.nextToken()) - 1;
                int c = Integer.parseInt(st.nextToken());
                int p = Integer.parseInt(st.nextToken());
                ap[i] = new AP(x, y, c, p);
            }

            sb.append("#").append(t).append(" ").append(sol()).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private int sol() {
        Point pA = new Point(0, 0); // 사용자 A의 초기 위치
        Point pB = new Point(SIZE - 1, SIZE - 1); // 사용자 B의 초기 위치

        // 충전 가능한 AP를 확인
        ArrayList<Integer> resA = checkMap(pA.x, pA.y);
        ArrayList<Integer> resB = checkMap(pB.x, pB.y);
        
        int ans = checkDuplicate(resA, resB); // 중복되는 AP 처리

        // 이동 후 매 시간마다 충전량 계산
        for (int i = 0; i < M; i++) {
            pA.x += direction[a[i]][0];
            pA.y += direction[a[i]][1];
            pB.x += direction[b[i]][0];
            pB.y += direction[b[i]][1];

            resA = checkMap(pA.x, pA.y);
            resB = checkMap(pB.x, pB.y);

            ans += checkDuplicate(resA, resB);
        }

        return ans;
    }

    // 주어진 위치에서 충전 가능한 AP 리스트 반환
    private ArrayList<Integer> checkMap(int x, int y) {
        ArrayList<Integer> res = new ArrayList<>();
        for (int k = 0; k < ap.length; k++) {
            if (ap[k].map[x][y]) {
                res.add(k);
            }
        }
        return res;
    }

    // 사용자 A와 B가 동일한 AP를 공유할 때 최적의 충전량 계산
    private int checkDuplicate(ArrayList<Integer> resA, ArrayList<Integer> resB) {
        resA.sort((a, b) -> ap[b].p - ap[a].p);
        resB.sort((a, b) -> ap[b].p - ap[a].p);

        if(resA.isEmpty() && resB.isEmpty()) {
            return 0;
        }
        if(resA.isEmpty()) {
            return ap[resB.get(0)].p;
        }
        if(resB.isEmpty()) {
            return ap[resA.get(0)].p;
        }
        if(resA.get(0) != resB.get(0)) {
            return ap[resA.get(0)].p + ap[resB.get(0)].p;
        }
        // 더 복잡한 조건들은 중복되는 AP가 있을 경우 두 사용자가 각각 다른 AP에서 최대한 충전을 하도록 계산
        return calculateMaxCharge(resA, resB);
    }

    // AP의 정보를 저장하고, AP의 충전 범위를 맵에 표시
    class AP {
        int x, y, c, p;
        boolean[][] map = new boolean[SIZE][SIZE];

        public AP(int x, int y, int c, int p) {
            this.x = x;
            this.y = y;
            this.c = c;
            this.p = p;
            initMap(x, y, c);
        }

        private void initMap(int x, int y, int c) {
            // AP의 충전 범위 계산 및 맵에 표시
            for (int i = x - c; i <= x + c; i++) {
                for (int j = y - c; j <= y + c; j++) {
                    if (i >= 0 && i < SIZE && j >= 0 && j < SIZE) {
                        map[i][j] = true;
                    }
                }
            }
        }
    }

    class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

시간 복잡도 분석

본 알고리즘은 각 시간마다 두 사용자의 위치를 업데이트하고, 각 위치에서 가능한 모든 AP에 대해 충전 가능성을 검사한다. 사용자의 이동에 따른 각 AP의 충전 가능 여부를 검사하는 데는 O(1) 시간이 소요되며, 모든 AP에 대해 검사하는데 O(A) 시간이 소요된다. 여기서 A는 AP의 총 수이다. 전체 시간 복잡도는 O(M×A)이며, M은 총 이동 횟수이다.

느낀점

이 문제를 통해 격자판에서의 위치 기반 최적화 문제를 해결하는 방법과 다수의 객체 간 상호작용을 계산하는 방법에 대해 학습할 수 있었다. 무선 충전과 같은 실생활 기술을 문제 해결에 적용해보는 것은 매우 흥미로운 경험이었다. 특히, 여러 사용자가 하나의 자원을 공유할 때 최적의 자원 배분 방법을 찾는 것은 다양한 분야에서 응용될 수 있는 중요한 개념이다.