[삼성 SW Expert Academy] 5644. [모의 SW 역량테스트] 무선 충전 [JAVA]

| Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

---

| Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

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

SW Expert Academy

---

| 풀이

1. step : MapMake 함수 -800*64
   - map을 3차원 배열로 만들었다. [ 행 ] [ 열 ] [ Battery Charger # ] - O(맵의 가로^2) * O(BC개수) = 최대 800
   
   - A,B 사람의 위치(행,열)로 부터 충전가능한 BC를 모두 탐색하기 위해 
   
   - 추후 2차원 반복문을 통해 모든 BC를 탐색한다. O(n^2) = 최대 64번
2. step : bfs - 200*64- bfs는 아니고 그냥 큐 사용ㅠ
   - A,B 사람을 큐로 관리 했다. - 큐 자료구조
   
   - 1) 매 time 마다 A,B 사람을 순서대로 꺼내고 - O(최대 이동시간) = 200 ( 100 * 2 )
   
   - 2) 위에서 만들어 준 3차원 배열 map과 입력받은 Battery Charger를 2중 for 반복 - O(n^2) = 64번
   
   - 3) 다음 이동할 방향을 다음 큐에 A,B 순서대로 넣어준다. - ap 객체 배열 참고 
3. 각 BC의 방문처리는 visited 1차원 배열로 처리 했다. 

---

| 어려웠던 점

• 일단, 올바른 풀이 방법은 아닌 것 같다. 디버깅 시간이 오래 걸렸고 약 3시간 소요. ㅠㅠ 

1. 행 과 열이 바뀌어서 관리 되기 때문에 매우 번거로웠다. -> 처음부터 기준을 잡아놓고 하는게 좋겠다.
2. visit을 어떻게 관리 해야하며, 모든 경우의 수를 탐색해야 하기 때문에 고민을 많이 했다.
   
   - map 자체를 객체로 선언하려 했으나 그렇게 되면 반복문을 통해 쉽게 접근하기 더 어려워서 
   - visit [ BC 의 개수 = # ] 으로 관리 했다.
   - ex. 해당 BC를 점유하면 visit 처리 후, B가 모든 BC 점유해보며 A와 동시 점유할 때와 아닐 때 비교
3. 아래 코드에서 보면, maxB와 maxA를 B사람이 모든 BC탐색하며 매번 초기화를 해줬어야 했는데 그러지 못해서 에러가 발생했고 해결했다. 
   
   ex. maxB와 maxA의 값이 바뀐뒤 새로운 BC에서 탐색할 때 조건문에서 maxA와 maxB 중 일부만 바뀔 수 있다.
4. sum = Math.max(maxA + maxB, sum) 을 for문 밖에 선언했는데 생각해보니, 매 경우의 수에서 최대값을 뽑아내는 거 목적이 었다. ==> for문 안쪽에서 sum 갱신
   
   그렇지 않다면, BC의 마지막 번호 값 기준으로 maxA와 maxB가 바뀌어서 sum이 계산된다.

---

| 코드

package 알고리즘공부하기;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 무선충전_sw5644 {

	static int[] dr = { 0, -1, 0, 1, 0 };
	static int[] dc = { 0, 0, 1, 0, -1 }; // 중앙 , 상 우 하 좌
	static int TC, M, A;
	static int[][] MoveInfo; // 사용자 이동 정보
	static AP[] ap; // ap 정보
	static int answer;
	static int[][][] map;
	static boolean[] visited;
	static final int SIZE = 10;
	static Queue<Point> q;

	// AP
	private static class AP {
		int x, y;
		int c, p;

		AP(int x, int y, int c, int p) {
			this.x = y;
			this.y = x;
			this.c = c;
			this.p = p;
		}
	}

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine(), " ");
		TC = Integer.parseInt(st.nextToken());

		for (int tc = 1; tc <= TC; tc++) {
			st = new StringTokenizer(br.readLine(), " ");
			M = Integer.parseInt(st.nextToken()); // 사람들 움직인 개수
			A = Integer.parseInt(st.nextToken()); // ap 개수

			MoveInfo = new int[M][2]; // 사람들 움직일 정보 {{A,B},{A,B}}
			ap = new AP[A]; // ap 정보
			map = new int[10][10][A]; // map 정보
			visited = new boolean[A]; // visit 정보에 따라 에너지 충전량 달라짐
			q = new LinkedList<>(); // 2 명의 사람 관리하는 큐
			answer = 0;

			for (int j = 0; j < 2; j++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int i = 0; i < M; i++) {
                	// 사람들 움직인 개수
					MoveInfo[i][j] = Integer.parseInt(st.nextToken()); 
				} // 사용자 움직이는 정보 저장
			}

			for (int i = 0; i < A; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				ap[i] = new AP(Integer.parseInt(st.nextToken()) - 1, 
                		Integer.parseInt(st.nextToken()) - 1,
						Integer.parseInt(st.nextToken()), 
                        Integer.parseInt(st.nextToken())
                        );
                        
				MapMake(ap[i], i);
			} // ap 정보 저장

			q.add(new Point(0, 0)); // A
			q.add(new Point(9, 9)); // B
			bfs();

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

	}

	private static void bfs() {
		int time = 0;
		while (time <= M) {
			// 1. 사용자 2명 꺼내기
			Point Aperson = q.poll(); // A
			Point Bperson = q.poll(); // B

			int sum = -1;
			// 2. 배열 돌면서 각 위치에 따른 최대 충전량 구하기
			for (int i = 0; i < A; i++) {
				int maxA = 0;
				int maxB = 0;

				// A사람이 충전이 된다면?
				if (map[Aperson.x][Aperson.y][i] > 0) {

					maxA = map[Aperson.x][Aperson.y][i]; // A의 최대값 바꿔주고
					visited[i] = true; // 방문처리
				}

				for (int j = 0; j < A; j++) {
					// B사람이 충전이 되는데
					maxA = map[Aperson.x][Aperson.y][i]; // A의 최대값 원상복구
					maxB = 0;
					if (map[Bperson.x][Bperson.y][j] > 0) {
						// A사람이랑 같은 ap라면?
						if (visited[j]) {
                        				// B는 해당 ap의 반절만
							maxB = map[Bperson.x][Bperson.y][j] / 2; 
                            			// A도 해당 ap의 반절로 줄이기
							maxA = map[Aperson.x][Aperson.y][i] / 2; 
						}
						// 같은 ap는 아니다
						else {
                        				// B는 온전히 충전량 다 가져감
							maxB = map[Bperson.x][Bperson.y][j]; 
						}

					}

					sum = Math.max(maxA + maxB, sum);
				}
				visited[i] = false; // 다시 바꿔주기
			}
//			System.out.println("time : " + time + " sum : " + sum );
			answer += sum;

			if (time == M)
				break;

			// 3. 이동하기 ( 2명 큐에 넣기 ) - 이동하지 않으면 그대로 충전하면 될듯

			int Adirect = MoveInfo[time][0]; // A가 움직일 방향
			int Bdirect = MoveInfo[time][1]; // B가 움직일 방향
			q.add(new Point(Aperson.x + dr[Adirect], Aperson.y + dc[Adirect]));
			q.add(new Point(Bperson.x + dr[Bdirect], Bperson.y + dc[Bdirect]));

			time++;

		}

	}

	private static void print() {
		for (int k = 0; k < A; k++) {
			for (int i = 0; i < SIZE; i++) {
				for (int j = 0; j < SIZE; j++) {
					System.out.print(map[i][j][k] + " ");
				}
				System.out.println();
			}
			System.out.println();
		}

	}

	private static void MapMake(AP ap, int idx) {
		int x = ap.x;
		int y = ap.y;

		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				int dist = Math.abs(x - i) + Math.abs(y - j);
				if (dist <= ap.c) {
					map[i][j][idx] = ap.p;
				}
			}
		}

	}
}

---

| 보완할 점

• 설명하기도 어려운 코드다.
• 명확한 코드 짜는 연습과 다른 방법 알아보기.

---