SWEA_무선충전_5644

1. 과정

- 2차원 리스트로 각 Battery Charger의 범위를 bfs로 돌며 저장한다.

- 두 사람의 경로대로 따라가며, 조건대로 더해주면 끝.

 

2. 구현

언어 : JAVA

메모리 : 37,060 kb

실행시간 : 207 ms

import java.util.*;

public class SWEA_무선충전_5644_O {
	static int N, M, answer;
	static int[] man1, man2;
	static boolean[][] visit;
	static int[] dr = { 0, -1, 0, 1, 0 };
	static int[] dc = { 0, 0, 1, 0, -1 };
	static ArrayList<Integer>[][] map;
	static ArrayList<BC> list;

	static class BC {
		int r, c, range, power;

		public BC(int r, int c, int range, int power) {
			this.r = r;
			this.c = c;
			this.range = range;
			this.power = power;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int testCase = 1; testCase <= T; ++testCase) {
			M = sc.nextInt();
			N = sc.nextInt();
			man1 = new int[M];
			man2 = new int[M];
			answer = 0;
			for (int i = 0; i < M; ++i)
				man1[i] = sc.nextInt();
			for (int i = 0; i < M; ++i)
				man2[i] = sc.nextInt();

			map = new ArrayList[10][10];
			for (int i = 0; i < 10; ++i) {
				for (int j = 0; j < 10; ++j) {
					map[i][j] = new ArrayList<Integer>();
				}
			}
			list = new ArrayList<>();
			for (int i = 0; i < N; ++i) {
				int c = sc.nextInt() - 1;
				int r = sc.nextInt() - 1;
				int range = sc.nextInt();
				int power = sc.nextInt();
				BC bc = new BC(r, c, range, power);
				// Battery Charger 정보 리스트에 저장
				list.add(bc);
				visit = new boolean[10][10];
				Queue<BC> q = new LinkedList<>();
				q.add(bc);
				// Battery Charger의 충전 범위를 체크함
				int level = 0;
				int num = i;
				visit[r][c] = true;
				map[r][c].add(num);
				while (!q.isEmpty()) {
					int qSize = q.size();
					for (int k = 0; k < qSize; ++k) {
						BC tbc = q.poll();
						r = tbc.r;
						c = tbc.c;
						int tr, tc;
						for (int j = 1; j <= 4; ++j) {
							tr = r + dr[j];
							tc = c + dc[j];
							if (tr < 0 || tc < 0 || tr >= 10 || tc >= 10 || visit[tr][tc])
								continue;
							visit[tr][tc] = true;
							map[tr][tc].add(num);
							q.add(new BC(tr, tc, range, power));
						}
					}
					level++;
					if (level == range)
						break;
				}
			}

			int r1 = 0;
			int c1 = 0;
			int r2 = 9;
			int c2 = 9;
			// 처음 자리 체크
			check(r1, c1, r2, c2);
			// 이동 방향에 따라 체크
			for (int i = 0; i < M; ++i) {
				r1 += dr[man1[i]];
				c1 += dc[man1[i]];
				r2 += dr[man2[i]];
				c2 += dc[man2[i]];
				check(r1, c1, r2, c2);
			}

			System.out.println("#" + testCase + " " + answer);
		}

	}

	private static void check(int r1, int c1, int r2, int c2) {
		ArrayList<Integer> list1 = map[r1][c1];	// 첫 번째 사람이 있는 장소에 포함되는 Battery Charger의 리스트
		ArrayList<Integer> list2 = map[r2][c2]; // 두 번째 사람이 있는 장소에 포함되는 Battery Charger의 리스트
		int max = 0;
		// 두 사람이 모두 충전 가능 한 경우
		if (list1.size() > 0 && list2.size() > 0) {
			// 충전할 수 있는 모든 경우의 수 중 가장 높은 파워를 충전 할 수 있는 값 더함
			for (int i = 0; i < list1.size(); ++i) {
				for (int j = 0; j < list2.size(); ++j) {
					max = Math.max(max, go(list1.get(i), list2.get(j)));
				}
			}
			answer += max;
		}
		// 첫 번째 사람만 충전 가능한 경우
		else if (list1.size() > 0) {
			// 모든 Battery Charger 리스트 중 가장 높은 파워를 가진 값 더함
			for (int i = 0; i < list1.size(); ++i) {
				int bc = list1.get(i);
				max = Math.max(max, list.get(bc).power);
			}
			answer += max;
		} 
		// 두 번째 사람만 충전 가능한 경우
		else if (list2.size() > 0) {
			// 모든 Battery Charger 리스트 중 가장 높은 파워를 가진 값 더함
			for (int i = 0; i < list2.size(); ++i) {
				int bc = list2.get(i);
				max = Math.max(max, list.get(bc).power);
			}
			answer += max;
		}
	}

	
	private static int go(int bc1, int bc2) {
		// 같은 BC를 사용 할 경우 총 충전량은 하나의 BC충전량과 같다.
		if (bc1 == bc2)
			return list.get(bc1).power;
		// 서로 다른 BC를 사용하는 경우 두 BC의 합과 같다.
		return list.get(bc1).power + list.get(bc2).power;
	}

}