[알고리즘] 무선 충전

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

SW Expert Academy

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.StringTokenizer;

public class Solution {
	
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= T; testCase++) {
			st = new StringTokenizer(br.readLine());
			int M = Integer.parseInt(st.nextToken());
			int A = Integer.parseInt(st.nextToken());
			int[] pathA = new int[M];
			int[] pathB = new int[M];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < M; i++) {
				pathA[i] = Integer.parseInt(st.nextToken());
			}
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < M; i++) {
				pathB[i] = Integer.parseInt(st.nextToken());
			}
			
			int[][] BC = new int[A][4];
			for (int i = 0; i < A; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < 4; j++) {
					BC[i][j] = Integer.parseInt(st.nextToken()); 
				}
			}
			
			List[][] map = new ArrayList[11][11];
			for (int i = 1; i < 11; i++) {
				for (int j = 1; j < 11; j++) {
					map[i][j] = new ArrayList<>();
				}
			}
			for (int i = 0; i < A; i++) {
				int col = BC[i][0];
				int row = BC[i][1];
				int distance = BC[i][2];
				
				paintMap(map, row, col, distance, i);
			}
			
			int[] dx = {0, -1, 0, 1, 0};
			int[] dy = {0, 0, 1, 0, -1};
			Point positionA = new Point(1, 1);
			Point positionB = new Point(10, 10);
			int energy = findBestEnergy(map, BC, positionA, positionB);
			for (int t = 0; t < M; t++) {
				positionA.translate(dx[pathA[t]], dy[pathA[t]]);
				positionB.translate(dx[pathB[t]], dy[pathB[t]]);
				energy += findBestEnergy(map, BC, positionA, positionB);
			}
			sb.append("#").append(testCase).append(" ").append(energy).append("\n");
		}
		System.out.println(sb);
	}

	private static int findBestEnergy(List[][] map, int[][] bC, Point positionA, Point positionB) {
		List<Integer> possibleA = map[positionA.x][positionA.y];
		List<Integer> possibleB = map[positionB.x][positionB.y];
		possibleA.add(-1);
		possibleB.add(-1);
		int maxEnergy = Integer.MIN_VALUE;
		for (int bcNumberA : possibleA) {
			for (int bcNumberB : possibleB) {
				int energy = 0;
				if (bcNumberA == -1 && bcNumberB == -1) {
					energy = 0;
				} else if (bcNumberA == -1) {
					energy = bC[bcNumberB][3];
				} else if (bcNumberB == -1) {
					energy = bC[bcNumberA][3];
				} else if (bcNumberA == bcNumberB) {
					energy = bC[bcNumberA][3];
				} else {
					energy = bC[bcNumberA][3] + bC[bcNumberB][3];
				}
				maxEnergy = Math.max(maxEnergy, energy);
			}
		}
		return maxEnergy;
	}

	private static void paintMap(List[][] map, int row, int col, int distance, int bcNumber) {
		
		boolean[][] visited = new boolean[11][11];
		int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
		int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};
		Deque<Point> deque = new ArrayDeque<>();
		deque.add(new Point(row, col));
		while (!deque.isEmpty()) {
			Point point = deque.poll();
			for (int i = 0; i < 8; i++) {
				int nr = point.x + dr[i];
				int nc = point.y + dc[i];
				if (!(1 <= nr && nr < 11 && 1 <= nc && nc < 11 && visited[nr][nc] == false)) {
					continue;
				}
				
				if (Math.abs(row - nr) + Math.abs(col - nc) <= distance) {
					map[nr][nc].add(bcNumber);
					visited[nr][nc] = true;
					deque.add(new Point(nr, nc));
				}
				
			}
		}
		
	}
}

나의 풀이

- position이 1, 1부터 시작하는 것을 간과하고 0,0부터 시작하는 것으로 해서 실패했다.

- 더미 값을 추가하면 예외처리가 쉬워진다.