[*5644*] 무선 충전 in Java (Feat. SWEA)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo 

SW Expert Academy

---

문제 요약 정리

최적의 BC를 선택하기
행과 열이 바뀌어있는 문제
단, BC 1과 BC 3의 충전 범위에 모두 속하기 때문에, 

이 위치에서는 두 BC 중 하나를 선택하여 접속할 수 있다.

1. 이동 가능 범위 구하기 -> bfs
bfs 깊이1 == C가 1일때
bfs 깊이2 = C가 2일때

 

 

2. 배터리 충전
매초마다 특정 BC의 충전 범위에 안에 들어오면 해당 BC에 접속이 가능
접속한 BC의 성능만큼 배터리 충전이 가능하다.
단, 두명의 접속자가 1개의 BC에 접속한 경우, 각각 충전양/사용자수 만큼 충전해준다.
같은 구역내에 있다 == 


모두 범위 밖일경우 -> 아무런 작업 x
A만 범위에 있는 경우 -> 최댓값 +
B만 범위에 있는 경우 -> 최댓값 +
A,B 모두 범위에 있는 경우 -> A랑 B가 같은 위치에 있을 경우 

무조건 큰 값 선택하기
A 선택 가능 : 1(500), 2(200)
B 선택 가능 : 1(500) 

A 선택 가능 : 1(200), 2(500)
B 선택 가능 : 1(200) 

10<=P<=500
500 10, 500
같은 위치에 도착했을 때
-> (1) (10,500) ==> 510
-> (2) (500,500) -> 250+250 == 500
1번이 더 효과적이다.

 

3. 모든 사용자가 충전한 양의 합의 최댓값을 구하라.

 

※ 제약 조건 ※ 
사용자 A는 BC 1과 3 둘 중 하나에 접속이 가능하다. 같은 시간에 사용자 B는 BC 1에 접속할 수 밖에 없다

 

---

 

 

문제 접근 방식

 

1. bfs로 무전기의 영역을 체크한다.

 

2. 사용자 A와 사용자 B를 동시에 움직이면서 

충전한 양의 합의 최댓값 구하기 --> move() 함수 참고

 

 

 

 

---

시행 착오

1.  dfs -> bfs로 변경함

: dfs로 풀다가 bfs로 변경했는데,

dfs로도 풀 수 있는 문제임에도 풀지 못했다 ㅠ.ㅠ

 

주말에  dfs로 다시 풀어보기

 

 

---

2.  A와 B가 모두 같은 범위에 있을때의 조건을

무전기 번호로 해야하는데

처음에 구현할 땐 c(범위), p(충전 처리량)이 같으면

같은 범위라고 인정해줘서 

테케 50개 중에 49개만 맞는 불상사가 일어남..

 

A,B가 모두 같은 범위 내에 있을때

최댓값을 구해주는 문제는

for문을 돌리면 되는 문제였다

(쏘씸플했던 부분..이었지만 나에겐 쏘하드했음)

 

 

 

 

---

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution {
    static ArrayList<Battery>[][] map;
    static final int N=10;
    static int[][] teamA; // A의 위치
    static int[][] teamB; // B의 위치
    static int[] dxs= {0,-1,0,1,0}; // 상,우,하,좌
    static int[] dys= {0,0,1,0,-1};
    static int[] moveA;
    static int[] moveB;
    static boolean[][] visited;
    static int M; // 이동 시간
    static int C; // 충전 범위
    static int P; // 처리량
    static int answer;
    
    static class Battery implements Comparable<Battery>{
        int x, y, c, p,no;
        
        public Battery(int x, int y, int c, int p,int no) {
            super();
            this.x = x;
            this.y = y;
            this.c = c;
            this.p = p;
            this.no=no;
        }
 
        @Override
        public int compareTo(Battery o) {
            return this.p!=o.p ? o.p-this.p :this.p-o.p; // 충전량 기준으로 내림차순 정렬
        }
        
    }
    
    public static boolean can_go(int x,int y) {
        return x>0 && x<=N && y>0 && y<=N && !visited[x][y];
    }
    
    // AP 범위 체크하는 함수
    public static void bfs(int depth, int x, int y, int no) { // no == 무전기 번호
        Queue<int[]> queue= new ArrayDeque<>(); // 자료형 배열로 변경
        queue.offer(new int[]{x,y,0,no});
        visited[x][y]=true; // 해당 칸 방문처리
        
        while(queue.size()!=0) {
            int[] curArr=queue.poll();
            int cx=curArr[0]; // 현재 x 좌표
            int cy=curArr[1]; // 현재 y 좌표
            int cnt=curArr[2]; // 현재 깊이
            visited[cx][cy]=true;
            
            if (cnt< C) {                
                for (int i = 1; i <5; i++) {
                    int nx=cx+dxs[i];
                    int ny=cy+dys[i];
                    if (can_go(nx,ny)) {
                        if (map[nx][ny]==null) { // 아무런 수가 채워져있지 않은 경우
                            map[nx][ny] = new ArrayList<Battery>();
                        }
                        map[nx][ny].add(new Battery(nx, ny,C,P,no)); // 충전 범위, 충전량
                        queue.offer(new int[] {nx,ny,cnt+1});
                    }
                }
            }
        }
    }
    
    // A,B 움직이기
    public static void move(int aX, int aY, int bX, int bY) {
        // 시작점 계산
        // A의 현재 위치
        int temp=Integer.MIN_VALUE;
        
        if (map[aX][aY]!=null) {
            if(map[bX][bY]!=null) {
                // A,B 모두 범위에 있는 경우
                for (Battery bA : map[aX][aY]) {
                    for (Battery bB : map[bX][bY]) {
                        if(bA.no==bB.no && bA.p==bB.p) {
                            temp=Math.max(temp, bA.p);
                        }else {
                            temp=Math.max(temp,bA.p+bB.p);
                        }
                    }
                }
            }else { 
                // A만 범위에 있는 경우 -> 최댓값 +
                for (Battery bA : map[aX][aY]) {
                    temp=Math.max(temp,bA.p);
                }
            }
        }else {
            if(map[bX][bY]!=null) {
                // B만 범위에 있는 경우 -> 최댓값 +
                for (Battery bB : map[bX][bY]) {
                    temp=Math.max(temp,bB.p);
 
                }
            } 
            // 모두 범위 밖일경우 -> 아무런 작업 x
            else{
                temp=0;
            }
        }
        answer+=temp;
        
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());        
        for (int t = 1; t <= T; t++) {
            answer=0;
            teamA=new int[1][2];
            teamB=new int[1][2];
            teamA[0][0]=1; teamA[0][1]=1;
            teamB[0][0]=N; teamB[0][1]=N;
            map=new ArrayList[N+1][N+1]; // 가로, 세로 크기는 10 (맵 정보 배열)
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            M=Integer.parseInt(st.nextToken()); // 총 이동시간
            int A=Integer.parseInt(st.nextToken()); // BC의 개수
            moveA=new int[M];
            moveB=new int[M];
            
            st = new StringTokenizer(br.readLine());
            
            // A의 이동정보
            for (int i = 0; i < M; i++) {
                moveA[i]=Integer.parseInt(st.nextToken());
            }
            
            // B의 이동정보
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                moveB[i]=Integer.parseInt(st.nextToken());
            }
            
            // AP의 위치정보(x,y), 충전 범위(C), 처리량(P)
            for (int i = 0; i < A; i++) {
                visited=new boolean[N+1][N+1]; // 가로, 세로 크기는 10 (방문 체크 배열)
                st = new StringTokenizer(br.readLine());
                int Y= Integer.parseInt(st.nextToken());
                int X=Integer.parseInt(st.nextToken());
                C=Integer.parseInt(st.nextToken()); // 충전범위 = 깊이
                P=Integer.parseInt(st.nextToken()); // 처리량 = 배터리 충전량
                if (map[X][Y]==null) {                    
                    map[X][Y]=new ArrayList<>();
                }
                map[X][Y].add(new Battery(X, Y, C, P, i+1)); // 충전범위, 충전량, 무전기 번호
                bfs(0,X,Y,i+1);
            }
            
            int aX = teamA[0][0];
            int aY = teamA[0][1];
            // B의 현재 위치
            int bX = teamB[0][0];
            int bY = teamB[0][1];
            move(aX,aY,bX,bY); // 초기위치 값 갱신
            
            for (int i = 0; i < M; i++) {                
                int direcA=moveA[i];
                int direcB=moveB[i];
                    
                // A 이동위치
                aX=aX+dxs[direcA];
                aY=aY+dys[direcA];
                
                // B 이동위치
                bX=bX+dxs[direcB];
                bY=bY+dys[direcB];
                move(aX,aY,bX,bY);
            }
            System.out.println("#"+t+" "+ answer);
        }
    }
}