두 사용자의 1초마다의 이동 경로가 주어진다.
각 초 마다 충전되는 양의 최댓값을 구하는 문제.
풀이 방법
map 을 3차원 배열로 선언 했다.
BC마다 충전 가능한 범위를 map에 표시 한다.
예를 들어 BC가 3개일 때 (1,2)위치는 BC 2로도 충전 가능하고 BC3으로도 충전 가능 하다면, map[1][2]={0,0,1,1,0} 이렇게 저장한다.
각 초 마다 사용자 두명 A,B를 이동 시킨다.
사용자가 서로 다른 BC로만 충전이 가능하다면 충전 양을 더해주기만 하면 된다.
문제는 사용자들이 충전 가능한 BC들이 겹쳐서 최대 경우를 따져 주어야 할 때이다.
map에 저장 해둔 배열의 값들을 각각 더해보면서 하나라도 2가 나온다면 충전 영역이 겹친다는 의미가 된다.
그런 상황이라면 A,B가 최대로 충전할 수 있는 조합을 찾는다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution_5644_무선충전 {
static int[][][] map;
static int M, A;
static int res;
static int[] pathA;
static int[] pathB;
static int[] power;
static int[] posA;
static int[] posB;
static int[][] dir = { { 0, 0 }, { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringTokenizer st = null;
for (int tc = 1; tc <= T; tc++) {
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
A = Integer.parseInt(st.nextToken());
map = new int[11][11][A + 1];
power = new int[A + 1];
pathA = new int[M + 1];
pathB = new int[M + 1];
posA = new int[] { 1, 1 };
posB = new int[] { 10, 10 };
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= M; i++) {
pathA[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= M; i++) {
pathB[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= A; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
power[i] = Integer.parseInt(st.nextToken());
map[x][y][i] = 1;
bfs(d,i, x, y); // 충전 영역 표시
}
if(isDiff()) { //A,B가 다른 영역에 있음
addPower(1,1);
addPower(10,10);
}else { //A,B가 같은 영역 안에 있음
checkMax();
}
for(int i=1;i<=M;i++) { // 이동
posA[0]+=dir[pathA[i]][0];
posA[1]+=dir[pathA[i]][1];
posB[0]+=dir[pathB[i]][0];
posB[1]+=dir[pathB[i]][1];
if(isDiff()) {
addPower(posA[0],posA[1]);
addPower(posB[0],posB[1]);
}else {
checkMax();
}
}
System.out.printf("#%d %d\n", tc, res);
res = 0;
}
}
private static void checkMax() { //A,B가 같은 영역에 있을 때
int[] p1 = map[posA[0]][posA[1]]; // A가 속한 영역들
int[] p2 = map[posB[0]][posB[1]]; // B가 속한 영역들
int maxPower = 0;
int tmp=0;
//A,B가 속한 영역들에서 충전 양이 최대가 되는 순서쌍 찾기
for(int i=1;i<=A;i++) {
if(p1[i]==1) {
for(int j=1;j<=A;j++) {
if(p2[j]==1) {
if(i==j) tmp = power[i]; //같은 BC에서 충전 할 때
else {
tmp = power[i]+power[j]; // 다른 BC
}
maxPower=Math.max(maxPower, tmp);
}
}
}
}
res+=maxPower;
}
private static void addPower(int x, int y) {
int maxPower = 0;
for(int i=1;i<=A;i++) { // 충전 양 최대인 BC 찾기
if(map[x][y][i]==1) {
maxPower=Math.max(maxPower, power[i]);
}
}
res+=maxPower;
}
private static boolean isDiff() { // A,B가 다른 영역에 있는지 판단
for(int i=1;i<=A;i++) {
if(map[posA[0]][posA[1]][i]+map[posB[0]][posB[1]][i]==2) { //어느 하나의 값이라도 2이면 영역 겹침
return false;
}
}
return true;
}
private static void bfs(int dist,int bc, int x, int y) {
boolean[][] visited = new boolean[11][11];
Queue<int[]> Queue = new LinkedList<>();
Queue.offer(new int[] { x, y, 0 });
visited[x][y] = true;
while (!Queue.isEmpty()) {
int[] now = Queue.poll();
for (int i = 1; i <= 4; i++) {
int nx = now[0] + dir[i][0];
int ny = now[1] + dir[i][1];
if(nx<0||nx>10||ny<0||ny>10 || visited[nx][ny]) continue;
visited[nx][ny]=true;
int d = now[2]+1;
if(d<=dist) {
map[nx][ny][bc]=1;
Queue.offer(new int[] {nx,ny,d});
}
}
}
}
}