알고리즘
[코드트리] 포탑 부수기 - 삼성SW역량테스트 기출문제
영리제리
2024. 7. 11. 17:27
일단 이 문제는요~ 쉬운데 어렵고 어려운데 쉬운 문제에요 ^^
깜찍이로 마음의 안정부터하고 시작~
문제 설명
문제 링크 (아래 사진 클릭)
요약
- NxM 크기의 격자에서 K번의 공격을 진행
- 다음의 4가지 순서를 반복 (*살아남은 포탑의 수가 1개 이하면 즉시 종료)
1. 공격자 선정
- 공격자 : 공격력이 가장 약한 포탑 => 공격력이 (N+M)만큼 증가함
- 대상자 : 공격력이 가장 강한 포탑
* 선정 기준
- Weak => 가장 약한 포탑
1. 같은 공격력을 가진 포탑이 여러개면, 가장 최근에 공격한 포탑이 Weak
2. 가장 최근에 공격한 포탑이 여러개면, (행 + 열)의 합이 가장 큰 포탑이 Weak
3. (행 + 열)이 같은 포탑이 여러개면, 열 값이 가장 큰 포탑이 Weak
- 따라서, 대상자는 공격자와 정반대
2. 공격자의 공격
- 레이저 공격: BFS 최단 경로 찾기
- 포탄 던지기: 8방향 진행
* 주의: 그래프 범위를 벗어나면 반대방향으로 진행됨.
3. 포탑 부서짐 => 공격력이 0이하가된 포탑은 부서짐.
4. 포탑 정비 => 이전 공격에 상관이 없던 포탑들은 공격력 1 증가
풀이
1. 포탑(Potop) 클래스 생성
- 필요한 필드 : 포탑 공격력, 마지막 공격 시간, x좌표, y좌표, 이전 턴에서 공격에 참여한 여부
- 포탑의 우선수위 설정 : Comparable 인터페이스 구현
static class Potop implements Comparable<Potop>{
int power, lastTime, x, y;
boolean isPre;
public Potop(int power, int lastTime, int x, int y, boolean isPre) {
this.power = power;
this.lastTime = lastTime;
this.x = x;
this.y = y;
this.isPre = isPre;
}
@Override
public int compareTo(Potop other) {
// 가장 약한 공격자 뽑기 우선순위
// 파워는 약한 순
if(this.power != other.power) return this.power - other.power;
// 시간은 가장 최근의 시간(큰 순)
if(this.lastTime != other.lastTime) return other.lastTime - this.lastTime;
// (행+열)은 큰 순
if(this.x+this.y != other.x+other.y) return (other.x+other.y) - (this.x+this.y);
// 열은 큰 순
return other.y - this.y;
}
public String toString(){
return "power: "+this.power+", lastTime: "+ this.lastTime + ", isPre: "+this.isPre + ", ("+x+","+y+")";
}
}
포탑이 영어로 뭔데요,,, ㅎㅎ 살면서 처음 들어봄,,, ㅎㅎ 변수명 짓는건 굉장해 엄청나 중요하지만요 귀엽게 짓는것도 꽤 중요해요 ^^
2. 공격자(Weak) & 대상자(Strong) 선정
포탑 클래스를 Comparable의 compareTo() 메소드로 우선수위를 정해 줬으니 정렬로 구할 수 있음.
// liveList : 살아있는 포탑 리스트
Collections.sort(liveList);
여담)
저는 처음에 우선순위큐(PriorityQueue)로 하면 되겠다! 생각하고, Comparator로 우선순위를 정해줄려고 했어요^^
이렇게요^^
PriorityQueue<Potop> wpq = new PriorityQueue<>(new Comparator<Potop>() {
@Override
public int compare(Potop p1, Potop p2) {
if(p1.power != p2.power) return p1.power - p2.power;
if(p1.lastTime != p2.lastTime) return p2.lastTime - p1.lastTime;
if((p1.x+p1.y) != (p2.x+p2.y)) return (p2.x+p2.y) - (p1.x+p1.y);
return p2.y - p1.y;
});
PriorityQueue<Potop> spq = new PriorityQueue<>(new Comparator<Potop>() {
@Override
public int compare(Potop p1, Potop p2) {
if(p1.power != p2.power) return p2.power - p1.power;
if(p1.lastTime != p2.lastTime) return p1.lastTime - p2.lastTime;
if((p1.x+p1.y) != (p2.x+p2.y)) return (p1.x+p1.y) - (p2.x+p2.y);
return p1.y - p2.y;
});딱 봐도 우선순위큐 두 개나 써야하고 복잡하고 그런거 보이죠~?? 여기선 이 방법이 유리하지 않아요 ㅎㅎ
그래도 우선순위큐 우선순위 지정하는 방법 언제간 쓸 일이 있으니깐 남겨둘게요 키키
3. BFS 최단 경로 찾기
bfs(너비우선탐색)으로 최단 거리를 구할 수 있다는 것은 모두모두 알고있죠?
(현재 노드와 거리가 1인 자식 노드들을 먼저 차례로 탐색하고 큐에 집어 넣은 뒤, 다시 그 자식들의 자식을 차례로 방문하면서, 목적 노드를 찾으면 중단하기 때문에 bfs로 찾은 거리는 최단거리라고 말할 수 있어요!)
그 런 데
"경로"는 어떻게 찾을까요,,,,,
(이 문제에서는 레이저가 훑고 가는 경로에 있는 포탑들도 영향을 받기 때문에 경로를 구해야 함)
결론적으로 말하면 이 부분을 구현하는데 많은 시행착오를 겪었고 결국 방법을 찾아본 뒤 구현하였어요.
따
란
1. Predecessor 리스트 추가
- 'predecessor'는 선배 노드를 의미
- 특정 노드에 오기 직전의 노드를 의미
=> 따라서, 특정 노드에 오기 직전의 노드를 기록한다.
2. 백트래킹(Backtracking)으로 경로 찾기
- 위에서 구한 predecessor 정보를 바탕으로 도착 노드를 시작으로 시작 노드까지의 최단 경로를 구한다.
- 예) p1 = 도착노드의 predecessor → p2 = p1의 predecessor …
....
// 경로의 포탑들
Pos pre = predecessor[strong.x][strong.y];
while (true) {
if (pre.x == weak.x && pre.y == weak.y) {
break;
}
p[pre.x][pre.y].power -= (weak.power / 2);
p[pre.x][pre.y].isPre = true;
pre = predecessor[pre.x][pre.y];
}
....
아! 그리고
그래프를 벗어난 경우 반대편에 영향을 끼치는 것
int nx = (now.x + rdx[i] + N) % N;
int ny = (now.y + rdy[i] + M) % M;
이렇게 아주 깔끔하게 범위를 정할 수 있습니다.
이제 코드를 적어볼게요~
코드
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int M;
static int K;
static Potop[][] p;
// 레이저 방향: 우하좌상
static int[] rdx = {0, 1, 0, -1};
static int[] rdy = {1, 0, -1, 0};
// 포탄던지기 방향 8방향
static int[] tdx = {0, 1, 0, -1, -1, -1, 1, 1};
static int[] tdy = {1, 0, -1, 0, -1, 1, -1, 1};
static class Potop implements Comparable<Potop>{
int power, lastTime, x, y;
boolean isPre;
public Potop(int power, int lastTime, int x, int y, boolean isPre) {
this.power = power;
this.lastTime = lastTime;
this.x = x;
this.y = y;
this.isPre = isPre;
}
@Override
public int compareTo(Potop other) {
// 가장 약한 공격자 뽑기 우선순위
// 파워는 약한 순
if(this.power != other.power) return this.power - other.power;
// 시간은 가장 최근의 시간(큰 순)
if(this.lastTime != other.lastTime) return other.lastTime - this.lastTime;
// (행+열)은 큰 순
if(this.x+this.y != other.x+other.y) return (other.x+other.y) - (this.x+this.y);
// 열은 큰 순
return other.y - this.y;
}
public String toString(){
return "power: "+this.power+", lastTime: "+ this.lastTime + ", isPre: "+this.isPre + ", ("+x+","+y+")";
}
}
static Potop weak;
static Potop strong;
static List<Potop> liveList;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
// 포탑 입력 및 초기화
p = new Potop[N][M];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
int power = Integer.parseInt(st.nextToken());
p[i][j] = new Potop(power, 0, i, j, false);
}
}
// K번 진행
for(int k=1; k<K+1; k++) {
// 살아있는 포탑 정리
liveList = new ArrayList<>();
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(p[i][j].power > 0) {
liveList.add(p[i][j]);
}
}
}
// 살아있는 포탑이 1개 이하면 중단
if(liveList.size() <= 1){
break;
}
find();
// System.out.println("w: "+weak);
// System.out.println("s: "+strong);
weak.power += (N+M);
// System.out.println("weak power : "+weak.power);
weak.isPre = true;
weak.lastTime = k;
if(!bfs(weak.x, weak.y)) {
// System.out.print("던지기 실행");
drop();
}
// System.out.println("공격후");
// print();
reward();
// System.out.println("정비후");
// print();
}
// 정답 출력
int ans = Integer.MIN_VALUE;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(p[i][j].power > ans){
ans = p[i][j].power;
}
}
}
System.out.println(ans);
}
public static void print() {
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
System.out.print("("+p[i][j].power +","+p[i][j].isPre+")");
}
System.out.println();
}
}
// 공격자와 대상자 찾기
public static void find() {
// 살아있는 포탑 정렬
Collections.sort(liveList);
// 2. 공격자와 대상자 찾기
weak = liveList.get(0);
strong = liveList.get(liveList.size()-1); // 대상자 조건은 공격자와 반대
}
static class Pos {
int x, y;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
public String toString() {
return "("+this.x+","+this.y+")";
}
}
public static boolean bfs(int sx, int sy) {
boolean[][] visited = new boolean[N][M];
Queue<Pos> q = new LinkedList<>();
Pos[][] predecessor = new Pos[N][M];
boolean isOk = false;
// predecessor 초기화
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
predecessor[i][j] = new Pos(0, 0);
}
}
visited[sx][sy] = true;
q.add(new Pos(sx, sy));
while(!q.isEmpty()) {
Pos now = q.poll();
if(now.x == strong.x && now.y == strong.y){
isOk = true;
break;
}
for(int i=0; i<4; i++) {
int nx = (now.x + rdx[i] + N) % N;
int ny = (now.y + rdy[i] + M) % M;
if(p[nx][ny].power != 0 && !visited[nx][ny]) {
visited[nx][ny] = true;
predecessor[nx][ny] = now;
q.add(new Pos(nx, ny));
}
}
}
if(!isOk) {
return isOk;
}
// 경로 출력
// for(int i=0; i<N; i++) {
// for(int j=0; j<M; j++) {
// System.out.print(predecessor[i][j]);
// }
// System.out.println();
// }
//경로의 포탑
Pos pre = predecessor[strong.x][strong.y];
while (true) {
if (pre.x == weak.x && pre.y == weak.y) {
break;
}
p[pre.x][pre.y].power -= (weak.power / 2);
p[pre.x][pre.y].isPre = true;
pre = predecessor[pre.x][pre.y];
}
// 대상자의 포탑
strong.power -= weak.power;
strong.isPre = true;
return isOk;
}
// 포탑 던지기
public static void drop() {
// 경로 포탑
for(int i=0; i<8; i++) {
int nx = (strong.x + tdx[i] + N) % N;
int ny = (strong.y + tdy[i] + M) % M;
if(nx == weak.x && ny == weak.y) {
continue;
}
if(p[nx][ny].power != 0) {
// System.out.println("("+nx+","+ny+")");
p[nx][ny].power -= (weak.power / 2);
p[nx][ny].isPre = true;
}
}
// 대상자 포탑
strong.power -= weak.power;
strong.isPre = true;
}
// 포탑 부서짐 & 포탑 정비
public static void reward() {
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(!p[i][j].isPre) {
if(p[i][j].power != 0){
p[i][j].power += 1;
}
} else{
// 이전에 공격 당했던 것들이 0보다 작으면 0으로 초기화
if(p[i][j].power < 0){
p[i][j].power = 0;
}
p[i][j].isPre = false;
}
}
}
}
}
주석이 너무 많다고요?
복잡하다고요?
읽기 어렵다고요?
그럴리가요?
도움이 정말 된다고요?
감사합니다~
