[SWEA/5644] 무선충전 - JAVA

🔗 문제 

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

SW Expert Academy

 

5644. 무선충전

---

📝 풀이

초기화
에너지를 직접 초기화할 배열과, 저장된 에너지의 근원지 번호를 저장할 배열을 선언한다.

에너지의 근원지가 저장된 리스트를 선언한다.

bfs를 통해 시작 지점으로부터 충전 가능한 지점까지 초기화 해주었다.
단, 겹치는 부분에 있어서는 디폴트로 큰 에너지를 가질 수 있도록 큰에너지를 우선 초기화해주었다.

 

이동
이동은 정지해 있을 때와 사방 탐색을 통해 진행한다.

같은 판 위에 두 명의 사람이 위치 하였을 때, 만약 서로의 에너지의 크기가 다르다면 어느 한 사람의 지점은 다른 에너지 판을 끌어다 사용할 수 있다는 의미이기 때문에, 둘 다 최적의 값을 충전 받을 수 있다.

같은 판 위에 두 명의 사람이 위치 하였을 때, 만약 서로의 에너지의 크기가 같다면, 세 가지의 경우의 수가 나올 수 있다.

1. A, B 모두 추가로 접근 가능한 다른 에너지가 있을 경우
   - 추가로접근 가능한 에너지와,  현재 위치의 가장 큰 에너지 두 에너지를 사용한다
   
   
2. A 혹은 B 만 접근 가능할 에너지가 있을 경우
   - A 혹은 B 만 접근 가능한 에너지와 현재 위치의 가장 큰 에너지를 사용한다
   
   
3. 결국 같은 에너지 판을 사용해야 할 경우
   한 에너지 판을 반으로 나누어 사용한다.

​

주의사항

사용 가능한 에너지의 크기로 공급 가능한지를 결정하기 때문에, 겹쳐있으면서 동시에 같은 에너지를 가진 판을 인식하지 못한다. 따라서 판의 위치와 번호를 저장한 배열을 통해 판별해주었다.

---

💻 코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class SW_5644_무선충전 {

	static int[][] map; // 맵 저장
	static int[][] check; // 번호 체커
	static ArrayList<int[]> orderEnergy = new ArrayList<>();

	static int M, A, sumA, sumB;
	static int rA, cA, rB, cB;
	static int[] mA, mB;

	// 정지 -> 상 -> 우 -> 하 -> 좌
	static int[] dx = { 0, -1, 0, 1, 0 };
	static int[] dy = { 0, 0, 1, 0, -1 };

	public static void main(String[] args) throws Exception {
  		System.setIn(new FileInputStream("input_SW_5644_무선충전.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int tc = Integer.parseInt(st.nextToken());

		for (int t = 1; t <= tc; t++) {
			st = new StringTokenizer(br.readLine());
			
			// 테스트 케이스마다 초기화
			M = Integer.parseInt(st.nextToken());
			A = Integer.parseInt(st.nextToken());

			mA = new int[M];
			mB = new int[M];
			map = new int[10][10];
			check = new int[10][10];
			rA = 0; cA = 0;
			rB = 9; cB = 9;
			sumA = 0; sumB = 0;
			orderEnergy.clear();

			// move input
			st = new StringTokenizer(br.readLine());
			StringTokenizer st2 = new StringTokenizer(br.readLine());
			for (int i = 0; i < M; i++) {
				mA[i] = Integer.parseInt(st.nextToken());
				mB[i] = Integer.parseInt(st2.nextToken());
			}

			for (int i = 0; i < A; i++) {
				st = new StringTokenizer(br.readLine());
				// X좌표 Y좌표가 반전이므로 반대로 넣음
				int c = Integer.parseInt(st.nextToken()) - 1;
				int r = Integer.parseInt(st.nextToken()) - 1;
				int dist = Integer.parseInt(st.nextToken());
				int energy = Integer.parseInt(st.nextToken());
				int no = i + 1;

				// bc 시작 위치 저장
				orderEnergy.add(new int[] { energy, dist, r, c });

				// bfs로 map 재배열
				bfs(r, c, dist, energy, no);
			}

			// 시작 지점 저장
			sumA = map[rA][cA];
			sumB = map[rB][cB];
			for (int i = 0; i < M; i++) 
				move(mA[i], mB[i]);
			
			System.out.println("#" + t + " " + (sumA + sumB));

		}
	}

	public static void move(int dirA, int dirB) {
		
		// 사람 A, B 다음 위치 저장
		int nrA = rA + dx[dirA];
		int ncA = cA + dy[dirA];

		int nrB = rB + dx[dirB];
		int ncB = cB + dy[dirB];

		// 같은 에너지 위에 존재
		if (map[nrA][ncA] == map[nrB][ncB] && map[nrA][ncA] != 0) {
			
			// 같은 에너지 이지만 다른 판에 위치했을 경우
			if (check[nrA][ncA] != check[nrB][ncB]) {
				sumA += map[nrA][ncA];
				sumB += map[nrB][ncB];
			} else {
				// 우선순위 큐로 접근 가능한 에너지중 큰 것부터 탐색
				PriorityQueue<Integer> queueA = new PriorityQueue<>(Collections.reverseOrder());
				PriorityQueue<Integer> queueB = new PriorityQueue<>(Collections.reverseOrder());

				// 해당 위치에서 에너지를 받을 수 있는 모든 경우의 수를 큐에 저장
				for (int i = 0; i < orderEnergy.size(); i++) {
					int[] tmp = orderEnergy.get(i);

					int distA = Math.abs(nrA - tmp[2]) + Math.abs(ncA - tmp[3]);
					int distB = Math.abs(nrB - tmp[2]) + Math.abs(ncB - tmp[3]);

					if (tmp[1] >= distA)
						queueA.offer(tmp[0]);
					if (tmp[1] >= distB)
						queueB.offer(tmp[0]);
				}

				int eA = queueA.poll();
				int eB = queueB.poll();

				// A, B 모두 추가적으로 접근 가능한 에너지가 있을 경우
				if (!queueA.isEmpty() && !queueB.isEmpty()) {
					if (queueA.peek() > queueB.peek())
						eA = queueA.poll();
					else
						eB = queueB.poll();
				} 
				// A에 접근 가능한 에너지가 있을 경우
				else if (!queueA.isEmpty())
					eA = queueA.poll();
				// B에 접근 가능한 에너지가 있을 경우
				else if (!queueB.isEmpty())
					eB = queueB.poll();
				
				// 결국 같은 에너지 판을 사용해야 할 경우
				else {
					eA = map[nrA][ncA] / 2;
					eB = map[nrA][ncA] / 2;
				}

				sumA += eA;
				sumB += eB;
			}
		}
		// 다른 위치 일때
		else {
			sumA += map[nrA][ncA];
			sumB += map[nrB][ncB];
		}

		// 위치 초기화
		rA = nrA;
		cA = ncA;
		rB = nrB;
		cB = ncB;
	}

	// BFS로 MAP에 에너지를 표시
	public static void bfs(int r, int c, int dis, int energy, int no) {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] { r, c, 0 });

		// Check 배열을 활용하여 이 에너지가 어떤 bc인지 표시
		if (map[r][c] < energy) {
			map[r][c] = energy;
			check[r][c] = no;
		}

		int second = 0;
		while (!queue.isEmpty() && second < dis) {
			int[] q = queue.poll();

			if (q[2] == dis)
				break;

			for (int i = 1; i <= 4; i++) {
				int nx = q[0] + dx[i];
				int ny = q[1] + dy[i];

				if (nx < 0 || ny < 0 || nx >= 10 || ny >= 10)
					continue;

				queue.offer(new int[] { nx, ny, q[2] + 1 });
				if (map[nx][ny] > energy)
					continue;

				// 에너지가 초기화 될 경우 해당 에너지가 어떤 bc인지 표시
				check[nx][ny] = no;
				
				// 에너지 초기화
				map[nx][ny] = energy;
			}
		}
	}
}