SWEA 1238 - 무선 충전

Java

1238 번 - 무선 충전

문제

BC의 정보와 사용자의 이동 궤적이 주어졌을 때, 모든 사용자가 충전한 양의 합의 최댓값을 구하는 프로그램을 작성하라.

접근 방법

꽤 복잡한 구현 문제였다.

각 배터리마다 범위를 표현하기 위해 3차원 배열을 사용하였다.
첫번째 인덱스는 각 배터리를 나타내고, 두번째/세번째 인덱스는 y,x값을 두어, 각 배터리마다 충전할 수 있는 범위를 나타내었다.

이제 A와 B가 각 시간마다 동시에 움직이게 하였다.
정해진 경로를 통해 한칸씩 움직이며, 각 좌표에 도달할 때 위치에서 배터리의 범위에 들어올 수 있으면 현재 배터리의 정보를 List에 저장한다.

이후 A와 B 마다 현재 충전 할 수있는 배터리의 정보가 들어있는 List의 배터리 값을 더해보며, 그 중 가장 세기가 큰 배터리의 합 값을 충전한다.

코드

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

class Solution {
	static int result = 0;
	static int[][][] map;
	public static void main(String []args) throws Exception {  
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	int tc = stoi(br.readLine());
    	
    	for(int tidx = 1; tidx <= tc; tidx++) {
    		result = 0;
    		int M, A;
    		stk = new StringTokenizer(br.readLine());
    		M = stoi(stk.nextToken());
    		A = stoi(stk.nextToken());
    		int[] aMove = new int[M + 1];
    		int[] bMove = new int[M + 1];
    		// A의 이동
    		stk = new StringTokenizer(br.readLine());
    		for(int i = 1; i <= M; i++) {
    			aMove[i] = stoi(stk.nextToken());
    		}
    		// B의 이동
    		stk = new StringTokenizer(br.readLine());
    		for(int i = 1; i <= M; i++) {
    			bMove[i] = stoi(stk.nextToken());
    		}
    		// 배터리의 범위를 설정한다.
    		map = new int[A + 1][11][11];
    		int[] bcValue = new int[A + 1];
    		for(int i = 1; i <= A; i++) {
    			stk = new StringTokenizer(br.readLine());
    			MakeBC(i, stoi(stk.nextToken()), stoi(stk.nextToken()), stoi(stk.nextToken()));
    			bcValue[i] = stoi(stk.nextToken());	 // BC의 세기
    		}
    		List<Integer> aBC = new ArrayList<Integer>();
    		List<Integer> bBC = new ArrayList<Integer>();
    		int ay = 1, ax = 1;		// A의 현재 좌표 
    		int by = 10, bx = 10;
    		
    		// 시간의 흐름
    		for(int t = 0; t <= M; t++) {
    			
    			ay += dy[aMove[t]];
    			ax += dx[aMove[t]];
    			by += dy[bMove[t]];
    			bx += dx[bMove[t]];
    			
    			aBC.clear();
    			bBC.clear();
    			
        		for(int i = 1; i <= A; i++) {
        			if(map[i][ay][ax] != 0) {
        				aBC.add(i);
        			}
        			if(map[i][by][bx] != 0) {
        				bBC.add(i);
        			}
        		}
    			
        		Collections.sort(bBC, (o1, o2)->{return -Integer.compare(bcValue[o1], bcValue[o2]);});
        		Collections.sort(aBC, (o1, o2)->{return -Integer.compare(bcValue[o1], bcValue[o2]);});
        		// 현재 B만 배터리 범위에 있는 경우
        		if(aBC.isEmpty() && !bBC.isEmpty()) {
        			result += bcValue[bBC.get(0)];
        		}
				// A만 배터리 범위에 있는 경우
        		else if(!aBC.isEmpty() && bBC.isEmpty()) {
        			result += bcValue[aBC.get(0)];
        		}
				// A,B 둘 다 배터리 범위에 있는 경우
        		else if(!aBC.isEmpty() && !bBC.isEmpty()){
        			int max = 0;
        			int sum = 0;
        			int curA, curB;
					// 현재 충전 할 수 있는 배터리 값의 합을 구하여 그 중 최대를 구한다.
        			for(int i = 0; i < aBC.size(); i++) {
            			for(int j = 0; j < bBC.size(); j++) {
            				curA = aBC.get(i);
            				curB = bBC.get(j);
            				if(curA == curB) {
            					max = Math.max(max, bcValue[curA]);
            				}
            				else {
            					sum = bcValue[curA] + bcValue[curB];
            					max = Math.max(max, sum);
            				}
            			}
        			}
        			result += max;
        		}
    		}	
    		System.out.println("#" + tidx + " " + result);
    	}
	}
	
	static int[] dy = {0, -1, 0, 1, 0};
	static int[] dx = {0, 0, 1, 0, -1};
	
	// 배터리 충전 범위들을 만들어 준다.  
	static void MakeBC(int idx, int x, int y, int time) {
		map[idx][y][x] = 1;
		
		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(y,x));
		
		int t = 0, cnt = 1, loop;
		int ny,nx;
		Point p;
		while(t < time) {			
			loop = cnt;
			cnt = 0;
			for(int k = 0; k < loop; k++) {
				p = queue.poll();
				y = p.y;
				x = p.x;
				for(int i = 1; i <= 4; i++) {
					ny = y + dy[i];
					nx = x + dx[i];
					
					if(isIn(ny,nx) && map[idx][ny][nx] == 0) {
						map[idx][ny][nx] = 1;
						queue.add(new Point(ny,nx));
						cnt++;
					}
				}
			}
			t++;
		}
	}
	
	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y == 0 || y >= 11 || x == 0 || x >= 11)
            return false;
        return true;
    }
    
    static class Point {
    	int y, x;

		public Point(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}
    }
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

좀 많이 꼬여서 복잡하게 푼 문제였다.

개선할 점

굳이 BFS로 미리 배터리 범위를 구할 필요 없이, 각 점마다 모든 배터리 위치를 비교하여([y1 - y2] + [x1 - x2]) 범위 내에 있는지만 확인하면 된다.