[SWEA] 5644 무선 충전 (D0 / 시뮬) - Java

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE&problemTitle=%EB%AC%B4%EC%84%A0+%EC%B6%A9%EC%A0%84&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

 

문제 해석

- 문제 해석
사용자가 BC(무선 충전 공간)에 들어오면 충전이 됨
충전기마다 성능이 다름 
성능 == 초당 충전량

범위가 겹치는 경우 둘 중 하나를 선택해서 사용이 가능함
같은 충전기를 같이 사용하는 경우 반반씩 사용할 수 있음

좌표 반대로 줌 (X, Y)
(1,1)부터 시작함

동시에 같은 위치로 이동할 수 있으며, 지도 밖으로 나가는 경우는 없음
모든 사용자가 지나가면서 충전할 수 있는 양의 최대 값을 구하라


- 각 테스트 케이스 별 입력
첫 번째 줄 : M A # M : 이동 시간 / A : BC 개수
두 번째 줄: A사용자 이동 정보 # 0 이동 없음 / 1 상 / 2 우 / 3 하/ 4 좌
세 번째 줄 : B사용자 이동 정보
나머지 줄  : X Y C P # (AP의 정보) X Y : 좌표 / C : 범위 / P : 성능

 

 

 

코드

import java.io.*;
import java.util.*;

public class Solution {

	static int[] dx = { 0, -1, 0, 1, 0 }; // 0 1 2 3 4
	static int[] dy = { 0, 0, 1, 0, -1 }; // 원위치 상 우 하 좌
	static int[] moveA;
	static int[] moveB;
	static int map[][][];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

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

		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine()); // 첫 번째 줄 입력
			int M = Integer.parseInt(st.nextToken()); // 이동 시간
			int A = Integer.parseInt(st.nextToken()); // BC 개수

			st = new StringTokenizer(br.readLine()); // 두 번쨰 줄 입력
			moveA = new int[M + 1];
			moveA[0] = 0;
			for (int i = 1; i <= M; i++) {
				moveA[i] = Integer.parseInt(st.nextToken());
			}

			st = new StringTokenizer(br.readLine()); // 세 번쨰 줄 입력
			moveB = new int[M + 1];
			moveB[0] = 0;
			for (int i = 1; i <= M; i++) {
				moveB[i] = Integer.parseInt(st.nextToken());
			}

			map = new int[A][11][11];
			for (int i = 0; i < A; i++) {
				st = new StringTokenizer(br.readLine()); // 나머지 줄 입력
				int Y = Integer.parseInt(st.nextToken());
				int X = Integer.parseInt(st.nextToken());
				int C = Integer.parseInt(st.nextToken());
				int P = Integer.parseInt(st.nextToken());

				makeBC(X, Y, C, P, i);
			}

			int answer = 0;

			int ax = 1;
			int ay = 1;
			int bx = 10;
			int by = 10;

			for (int i = 0; i < M + 1; i++) {
				ax = ax + dx[moveA[i]];
				ay = ay + dy[moveA[i]];
				bx = bx + dx[moveB[i]];
				by = by + dy[moveB[i]];
				LinkedList<Integer> aCan = new LinkedList<>();
				aCan.add(0);
				LinkedList<Integer> bCan = new LinkedList<>();
				bCan.add(0);
				for (int j = 0; j < map.length; j++) {
					if (map[j][ax][ay] != 0) {
						aCan.add(map[j][ax][ay]);
					}
					if (map[j][bx][by] != 0) {
						bCan.add(map[j][bx][by]);
					}
				}

				Collections.sort(aCan);
				Collections.sort(bCan);

				int aCanLast = aCan.get(aCan.size() - 1);
				int bCanLast = bCan.get(bCan.size() - 1);

				if (aCanLast == 0 || bCanLast == 0) {
					answer += aCanLast + bCanLast;
//					System.out.println(aCanLast + " " + bCanLasst);
				} else if (aCanLast == bCanLast) {
					int aIdx = 0;
					int bIdx = 0;
					for (int j = 0; j < map.length; j++) {
						if (aCanLast == map[j][ax][ay]) {
							aIdx = j;
						}
					}
					for (int j = 0; j < map.length; j++) {
						if (bCanLast == map[j][bx][by]) {
							bIdx = j;
						}
					}

					if (aIdx == bIdx) {
						int maxSame = aCanLast;
						aCanLast = aCan.get(aCan.size() - 2);
						bCanLast = bCan.get(bCan.size() - 2);

						answer += maxSame + Math.max(aCanLast, bCanLast);
					} else {
						answer += aCanLast + bCanLast;
					}

				} else {
					answer += aCanLast + bCanLast;
				}

			}

			System.out.println("#" + test_case + " " + answer);

		} // [E] test_case
	}

	static class Point {
		int x;
		int y;
		int c;
		int p;
		int a;

		public Point(int x, int y, int c, int p, int a) {
			this.x = x;
			this.y = y;
			this.c = c;
			this.p = p;
			this.a = a;
		}
	}

	private static void makeBC(int X, int Y, int C, int P, int A) {
		Queue<Point> q = new LinkedList<>();
		q.offer(new Point(X, Y, C, P, A));

		while (!q.isEmpty()) {
			Point p = q.poll();
			for (int d = 0; d < dx.length; d++) {
				int cx = p.x + dx[d];
				int cy = p.y + dy[d];
				if (cx >= 0 && cx < map[0].length && cy >= 0 && cy < map[0][0].length) {
					map[p.a][cx][cy] = p.p;
					if (p.c - 1 > 0) {
						q.offer(new Point(cx, cy, p.c - 1, p.p, p.a));
					}
				}
			}
		}

	}

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

 

 

 

코드 해석

BC의 X와 Y가 반대로 들어오는데 유의해야 합니다.

 

BC의 범위는 BFS의 확산처럼 진행되므로 BFS를 통하여 구현하였습니다. (공식을 이용해서 구할 수 있었습니다.)

 

 

각 BC의 범위 판단을 위해서 3차원 배열을 사용하였습니다.

공식을 사용한다면 BC 범위 판단을 굳이 3차원 배열을 사용할 필요가 없습니다.

 

 

 

발생한 문제 & 해결 방안

동시에 이동한다는 문구가 나오면 map에서 이동시키는 문제가 아니다!

-> for, if 조건을 통한 해결

 

X, Y가 반대로 들어오는 문제여서 한 번 꼬였다.

-> 문제를 다시 잘 읽어보자!

 

테스트 케이스 45개에서 틀렸다면 같은 파워를 가진 다른 충전기가 있는데 그걸 고려하지 않은 것이다. 

-> 문제를 잘 읽어야한다!

 

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice