[SWEA] - 무선 충전 / 5644번 (Java)
1. 문제 접근
모든 사용자의 충전량 합의 최대값을 구하면 된다.
사용자는 A, B 2명만 존재하며, 주어진 시간 `totalTime` 동안 이동시킨다.
문제에서 주어진 그림을 기준으로 상하좌우를 보면 아래와 같이 이동한다.
- 상(열 감소)
- 우(행 증가)
- 하(열 증가)
- 좌(행 감소)
또, A B 2명이 항상 큰 충전량을 가지는 BC를 선택하기 위해 BC의 충전량을 기준으로 내림차순 정렬한다.
// BC 클래스
static class BC implements Comparable<BC>{
Pos pos;
int limitDist;
int power;
public BC(int xPos, int yPos, int limitDist, int power) {
pos = new Pos(xPos, yPos);
this.limitDist = limitDist;
this.power = power;
}
// 충전량이 큰 순서대로 정렬하기 위해서 사용
@Override
public int compareTo(BC o) {
return o.power - this.power;
}
}
기본적인 아이디어는 다음과 같다.
현재 A, B의 좌표에서 모든 BC와의 거리를 확인한다.
int distAandBC = getDist(aPos, currCheckingBC.pos);
int distBandBC = getDist(bPos, currCheckingBC.pos);
BC와의 거리가 BC의 사정거리 내에 있을 경우 각각의 연결 가능한 BC 리스트를 저장하는 리스트(`bcListA`, `bcListB`)에 저장한다.
// A가 현재 BC의 사거리 내에 있는 경우
if(distAandBC<=currCheckingBC.limitDist) {
// A의 연결 가능 BC 리스트에 추가
bcListA.add(currCheckingBC);
}
// B가 현재 BC의 사거리 내에 있는 경우
if(distBandBC<=currCheckingBC.limitDist) {
// B의 연결 가능 리스트에 추가
bcListB.add(currCheckingBC);
}
A, B 둘이 서로 연결 가능한 BC가 겹치지 않을 경우
- 각각의 연결 가능한 BC 리스트 중 최대 충전량을 보유한 BC에 연결한다.
A, B 둘이 서로 연결 가능한 BC가 겹치는 경우
-
- A가 연결 가능한 BC 리스트에서 하나 선택, B가 연결 가능한 BC 리스트에서 하나 선택한다
- 이 때, A가 이미 연결한 BC라면, PASS
- B에서 BC를 연결했다면, 최대 충전량을 갱신한다.
이 때, A가 연결 가능한 BC 가 없을 경우, B가 연결 가능한 BC가 있음에도 확인할 수 없어진다. 따라서, B를 먼저 선택하는 경우도 고려해야한다.
// currSum: 최종적인 A, B의 충전량
int currSum = 0;
// 조합: bcListA에서 1개 선택, bcListB에서 한개 선택
for (BC aBC : bcListA) {
int localSum = 0;
int xPosA = aBC.pos.xPos;
int yPosA = aBC.pos.yPos;
// 해당 BC를 사용 중이라고 표시
isAlreadyConnected[xPosA][yPosA] = true;
localSum += aBC.power;
for (BC bBC : bcListB) {
int xPosB = bBC.pos.xPos;
int yPosB = bBC.pos.yPos;
if (isAlreadyConnected[xPosB][yPosB])
continue;
// 해당 BC가 사용중이지 않다면 충전량을 더한다.
localSum += bBC.power;
break;
}
// 이후 탐색을 위한 후처리
isAlreadyConnected[xPosA][yPosA] = false;
// 최대 충전량 갱신
currSum = Math.max(localSum, currSum);
}
충전량 계산이 끝나면 A, B를 한 칸씩 입력에서 주어진대로 이동한다.
2. 코드
package swea;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
/**
* 무선 충전
* @author JinHxxxxKim
*
* 1. 총 테스트 케이스의 개수 TC를 입력받는다.
* 2. 총 이동 시간(M), BC의 개수(A)를 입력받는다
* 3. A와 B의 이동 정보를 입력받는다.
* 4. M개의 줄에 걸쳐 BC의 정보를 입력받는다.
*
* 0: 정지, 1: 상(열 감소), 2: 우(행 증가), 3: 하(열 증가), 4:좌(행 감소)
*
* 이동 시간 만큼 반복하며 확인
*
* 1. A, B의 좌표에서 모든 BC와의 거리를 확인한다.
* 2. BC와의 거리가 BC의 사정거리 내에 있을 경우 연결 가능
* 3. 연결 가능한 BC 중 파워가 가장 큰 BC에 연결
*
* 연결 가능한 BC가 있다면 각각의 BC리스트에 add
* - 각각의 BC리스트의 크기가 0 == 해당 시간에 충전을 못하는 경우
*
* A, B 둘이 서로 연결 가능한 BC가 겹치지 않을 경우는 문제X
*
* 겹치는 경우가 문제
* 해결 방법:
* - A가 연결 가능한 BC 리스트에서 하나 선택, B가 연결 가능한 BC 리스트에서 하나 선택한다.
* - 이 때, A가 이미 연결한 BC라면, PASS
* - B에서 BC를 연결했다면, 최대 충전량을 갱신한다.
*
* A가 연결 가능한 BC 가 없을 경우, B가 연결 가능한 BC가 있음에도 확인할 수 없어진다.
* 따라서, B를 먼저 선택하는 경우도 고려해야한다.
*
* - B가 연결 가능한 BC 리스트에서 하나 선택, B가 연결 가능한 BC 리스트에서 하나 선택한다.
* - 이 때, B가 이미 연결한 BC라면, PASS
* - A에서 BC를 연결했다면, 최대 충전량을 갱신한다.
*/
public class Sol_5644 {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static StringBuilder sb = new StringBuilder();
private static StringTokenizer st;
private static int totalTime; // 총 이동 시간
private static int totalBCNumber; // 총 BC 개수
private static int[] movingA; // A의 이동정보
private static int[] movingB; // B의 이동정보
private static BC[] bcInfo; // BC정보
private static int powerSum;
private static Pos aPos;
private static Pos bPos;
public static void main(String[] args) throws Exception {
int TC = Integer.parseInt(br.readLine().trim());
for (int testCase = 1; testCase <= TC; testCase++) {
// 총 이동 시간, 총 BC 개수 입력
st = new StringTokenizer(br.readLine().trim());
totalTime = Integer.parseInt(st.nextToken());
totalBCNumber = Integer.parseInt(st.nextToken());
// A의 이동정보, B의 이동정보 입력
movingA = new int[totalTime];
movingB = new int[totalTime];
st = new StringTokenizer(br.readLine().trim());
for(int timeCnt = 0;timeCnt<totalTime;++timeCnt) {
movingA[timeCnt] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine().trim());
for(int timeCnt = 0;timeCnt<totalTime;++timeCnt) {
movingB[timeCnt] = Integer.parseInt(st.nextToken());
}
// BC정보 입력
bcInfo = new BC[totalBCNumber];
for (int bcCnt = 0; bcCnt < totalBCNumber; ++bcCnt) {
st = new StringTokenizer(br.readLine().trim());
int xPos = Integer.parseInt(st.nextToken())-1;
int yPos = Integer.parseInt(st.nextToken())-1;
int limitDist = Integer.parseInt(st.nextToken());
int power = Integer.parseInt(st.nextToken());
bcInfo[bcCnt] = new BC(xPos, yPos, limitDist, power);
}
// 로직 시작
powerSum = 0;
// A, B 초기위치 설정
aPos = new Pos(0, 0);
bPos = new Pos(9, 9);
// 출력이 강한 순서대로 정렬
Arrays.sort(bcInfo);
solution();
sb.append(String.format("#%d %d\n", testCase, powerSum));
}
System.out.println(sb);
}
private static void solution() {
// 모든 시간대 별로 확인
// 초기 A의 위치 = [0, 0]
// 초기 B의 위치 = [9, 9]
for (int currTime = 0; currTime <= totalTime; ++currTime) {
// A, B의 현재 위치에 대해 연결 가능한 BC를 저장할 리스트
List<BC> bcListA = new ArrayList<>();
List<BC> bcListB = new ArrayList<>();
// B가 BC에 연결하려 할 때, 이미 A가 연결한 상태인지 확인하기 위한 배열
// BC 구분을 위해 BC의 좌표를 사용
boolean[][] isAlreadyConnected = new boolean[10][10];
// 모든 BC 순회
for (int bcNum = 0; bcNum < totalBCNumber; ++bcNum) {
BC currCheckingBC = bcInfo[bcNum];
int distAandBC = getDist(aPos, currCheckingBC.pos);
int distBandBC = getDist(bPos, currCheckingBC.pos);
// A가 현재 BC의 사거리 내에 있는 경우
if(distAandBC<=currCheckingBC.limitDist) {
// A의 연결 가능 BC 리스트에 추가
bcListA.add(currCheckingBC);
}
// B가 현재 BC의 사거리 내에 있는 경우
if(distBandBC<=currCheckingBC.limitDist) {
// B의 연결 가능 리스트에 추가
bcListB.add(currCheckingBC);
}
}
// currSum: 최종적인 A, B의 충전량
int currSum = 0;
// 조합: bcListA에서 1개 선택, bcListB에서 한개 선택
for (BC aBC : bcListA) {
int localSum = 0;
int xPosA = aBC.pos.xPos;
int yPosA = aBC.pos.yPos;
// 해당 BC를 사용 중이라고 표시
isAlreadyConnected[xPosA][yPosA] = true;
localSum += aBC.power;
for (BC bBC : bcListB) {
int xPosB = bBC.pos.xPos;
int yPosB = bBC.pos.yPos;
if (isAlreadyConnected[xPosB][yPosB])
continue;
// 해당 BC가 사용중이지 않다면 충전량을 더한다.
localSum += bBC.power;
break;
}
// 이후 탐색을 위한 후처리
isAlreadyConnected[xPosA][yPosA] = false;
// 최대 충전량 갱신
currSum = Math.max(localSum, currSum);
}
// 조합: bcListB에서 1개 선택, bcListA에서 한개 선택
for (BC bBC : bcListB) {
int localSum = 0;
int xPosB = bBC.pos.xPos;
int yPosB = bBC.pos.yPos;
// 해당 BC를 사용 중이라고 표시
isAlreadyConnected[xPosB][yPosB] = true;
localSum += bBC.power;
for (BC aBC : bcListA) {
int xPosA = aBC.pos.xPos;
int yPosA = aBC.pos.yPos;
if (isAlreadyConnected[xPosA][yPosA])
continue;
// 해당 BC가 사용중이지 않다면 충전량을 더한다.
localSum += aBC.power;
break;
}
// 이후 탐색을 위한 후처리
isAlreadyConnected[xPosB][yPosB] = false;
// 최대 충전량 갱신
currSum = Math.max(localSum, currSum);
}
powerSum += currSum;
// 한 턴이 끝나면 이동
if(currTime==totalTime)
break;
move(currTime);
}
}
// 이동 메소드
// 0: 정지, 1: 상(열 감소), 2: 우(행 증가), 3: 하(열 증가), 4:좌(행 감소)
private static void move(int time) {
// A 이동
switch (movingA[time]) {
case 0:
// 정지
break;
case 1:
// 상
aPos.yPos -= 1;
break;
case 2:
// 우
aPos.xPos += 1;
break;
case 3:
// 하
aPos.yPos += 1;
break;
case 4:
// 좌
aPos.xPos -= 1;
break;
default:
break;
}
// B 이동
switch (movingB[time]) {
case 0:
// 정지
break;
case 1:
// 상
bPos.yPos -= 1;
break;
case 2:
// 우
bPos.xPos += 1;
break;
case 3:
// 하
bPos.yPos += 1;
break;
case 4:
// 좌
bPos.xPos -= 1;
break;
default:
break;
}
}
// 두 점 사이의 거리 계산 메소드
private static int getDist(Pos srcPos, Pos destPos) {
int dist = 0;
dist += Math.abs(srcPos.xPos-destPos.xPos);
dist += Math.abs(srcPos.yPos-destPos.yPos);
return dist;
}
// 위치 클래스
static class Pos {
int xPos;
int yPos;
public Pos(int xPos, int yPos) {
super();
this.xPos = xPos;
this.yPos = yPos;
}
}
// BC 클래스
static class BC implements Comparable<BC>{
Pos pos;
int limitDist;
int power;
public BC(int xPos, int yPos, int limitDist, int power) {
pos = new Pos(xPos, yPos);
this.limitDist = limitDist;
this.power = power;
}
// 출력이 강한 숭서대로 정렬하기 위함
@Override
public int compareTo(BC o) {
return o.power - this.power;
}
}
}3. 디버깅
처음에 발상할 당시, 무조건 A가 먼저 BC를 선택하고, B가 나중에 선택하면 맞겠구나 생각했다가 틀렸었다.
문제는 A가 접근 가능한 BC가 여러개가 존재하고, B가 접근 가능한 BC가 하나 있을 경우, B가 접근 가능한 유일한 BC가 A역시 접근 가능할 때였다.
발상대로 무조건 A가 먼저 BC에 접근할 경우, B는 유일한 접근 가능한 BC를 접근할 수 없게 되고, 이는 A가 다른 BC에 접근하고, B가 유일한 BC에 접근할 경우보다 충전량이 적을 수 밖에 없다.
따라서, 무조건 A가 먼저 BC를 선택하는 것이 아닌 A가 접근 가능한 BC에서 한개, B가 접근 가능한 BC에서 한개 선택해서 모든 조합을 선택해 본 뒤, 최대의 충전량을 갖는 조합을 선택하도록 수정했다.
조금 더 꼼꼼하게 경계지점을 처리하도록 해야겠다.
4. 결과
'알고리즘' 카테고리의 다른 글
| [BOJ] - 줄세우기 / 2252번 (Java) (0) | 2024.02.20 |
|---|---|
| [SWEA] - 상호의 배틀필드 / 1873번 (Java) (1) | 2024.02.15 |
| [SWEA] - 최적 경로 / 1247번 (Java) (0) | 2024.02.15 |
| [BOJ] - 신기한 소수/2023번 (JAVA) (0) | 2024.02.14 |
| [BOJ] - 공유기 설치/2110번 (JAVA) (0) | 2024.02.14 |