[알고리즘] 루돌프의 반란
2024. 3. 24. 23:11ㆍ알고리즘 풀이/Java
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
static class Santa {
int id;
int score;
Point point;
boolean isStunned;
int whenNotStunned;
boolean isDied;
public Santa(int id, int score, Point point, int power, boolean isStunned,
int whenNotStunned) {
this.id = id;
this.score = score;
this.point = point;
this.isStunned = isStunned;
this.whenNotStunned = whenNotStunned;
this.isDied = false;
}
@Override
public String toString() {
return "Santa{" +
"id=" + id +
", score=" + score +
", point=" + point +
", isStunned=" + isStunned +
", whenNotStunned=" + whenNotStunned +
'}';
}
}
static class Dog {
Point point;
public Dog(Point point) {
this.point = point;
}
@Override
public String toString() {
return "Dog{" +
"point=" + point +
'}';
}
}
static int N;
static int M;
static int P;
static int C;
static int D;
static TreeSet<Santa> santas;
static Dog dog;
static int[] finalScore;
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());
P = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
finalScore = new int[P + 1];
st = new StringTokenizer(br.readLine());
dog = new Dog(
new Point(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1));
santas = new TreeSet<>(new Comparator<Santa>() {
@Override
public int compare(Santa o1, Santa o2) {
return o1.id - o2.id;
}
});
for (int i = 1; i <= P; i++) {
st = new StringTokenizer(br.readLine());
Santa santa = new Santa(Integer.parseInt(st.nextToken()), 0,
new Point(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1),
D,
false, 0);
santas.add(santa);
}
for (int i = 1; i <= M; i++) {
playRound();
// System.out.println("round = " + i);;
// System.out.println(dog);
// for (Santa santa : santas) {
// System.out.println(santa);
// }
// for (int j = 1; j < finalScore.length; j++) {
// if (finalScore[j] != 0) {
// System.out.println("score " + j + " " + finalScore[j]);
// }
// }
// System.out.println();
}
StringBuilder sb = new StringBuilder();
for (Santa santa : santas) {
finalScore[santa.id] = santa.score;
}
for (int i = 1; i < finalScore.length; i++) {
sb.append(finalScore[i]).append(" ");
}
System.out.println(sb);
}
private static void playRound() {
// 산타가 모두 탈락이라면 게임 종료
if (santas.isEmpty()) {
return;
}
dogMove();
santasMove();
// 기절 산타 갱신
for (Santa santa : santas) {
if (santa.isStunned) {
if (santa.whenNotStunned == 0) {
santa.isStunned = false;
} else {
santa.whenNotStunned--;
}
}
}
// 점수 + 1
for (Santa santa : santas) {
santa.score++;
}
}
private static void santasMove() {
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
List<Santa> removeSanta = new ArrayList<>();
for (Santa santa : santas) {
if (santa.isStunned || santa.isDied) {
continue;
}
Integer dir = moveS(santa, dx, dy);
if (dir == null) {
continue;
}
Point point;
// 루돌프와의 충돌 확인
if (!dog.point.equals(santa.point)) {
continue;
}
// santa 점수 증가
santa.score += D;
// santa 기절
santa.isStunned = true;
santa.whenNotStunned = 1;
// santa 이동
point = santa.point;
// System.out.println("before " + santa);
int nr = point.x - dx[dir] * D;
int nc = point.y - dy[dir] * D;
// System.out.println(nr + " " + nc);
if (validateRange(new Point(nr, nc))) {
// santa 이동
santa.point.setLocation(nr, nc);
} else {
// 최종 점수 등록
finalScore[santa.id] = santa.score;
// 삭제
removeSanta.add(santa);
santa.isDied = true;
continue;
}
while (isBakSal(santa)) {
santa = afterCollide(santa, (dir + 2) % 4, new int[] {-1, 0, 1, 0}, new int[] {0, 1, 0, -1}, removeSanta);
if (santa == null) {
break;
}
}
}
for (Santa santa : removeSanta) {
santas.remove(santa);
}
}
private static Integer moveS(Santa santa, int[] dx, int[] dy) {
Point point = null;
int minDis = (int)(Math.pow(santa.point.x - dog.point.x, 2) + Math.pow(santa.point.y - dog.point.y, 2));
int dir = -1;
for (int i = 0; i < 4; i++) {
int nr = santa.point.x + dx[i];
int nc = santa.point.y + dy[i];
if (!validateRange(new Point(nr, nc))) {
continue;
}
if (!validateCollide(new Point(nr, nc))) {
continue;
}
int dr = dog.point.x - nr;
int dc = dog.point.y - nc;
int dis = (int)(Math.pow(dr, 2) + Math.pow(dc, 2));
if (dis < minDis) {
minDis = dis;
dir = i;
}
}
if (dir != -1) {
int nr = santa.point.x + dx[dir];
int nc = santa.point.y + dy[dir];
santa.point.setLocation(nr, nc);
} else {
return null;
}
return dir;
}
private static boolean validateCollide(Point point) {
for (Santa santa1 : santas) {
if (santa1.isDied) {
continue;
}
if (point.equals(santa1.point)) {
return false;
}
}
return true;
}
private static void dogMove() {
Santa santa = findSanta();
int dir = move(santa);
if (isCollied()) {
collide(dir);
}
while (isBakSal(santa)) {
santa = afterCollide2(santa, dir, new int[] {-1, -1, -1, 0, 0, 1, 1, 1}, new int[] {-1, 0, 1, -1, 1, -1, 0, 1});
if (santa == null) {
break;
}
}
}
private static Santa afterCollide(Santa santa, int dir, int[] dr, int[] dc, List<Santa> removeSanta) {
for (Santa santa1 : santas) {
if (santa1.isDied) {
continue;
}
if (!santa.equals(santa1) && santa.point.equals(santa1.point)) {
// santa 이동
Point point = santa1.point;
int nr = point.x + dr[dir];
int nc = point.y + dc[dir];
if (validateRange(new Point(nr, nc))) {
// santa 이동
santa1.point.setLocation(nr, nc);
return santa1;
} else {
// 최종 점수 등록
finalScore[santa1.id] = santa1.score;
// 삭제
removeSanta.add(santa1);
// santas.remove(santa1);
return null;
}
}
}
return null;
}
private static Santa afterCollide2(Santa santa, int dir, int[] dr, int[] dc) {
for (Santa santa1 : santas) {
if (santa1.isDied) {
continue;
}
if (!santa.equals(santa1) && santa.point.equals(santa1.point)) {
// santa 이동
Point point = santa1.point;
int nr = point.x + dr[dir];
int nc = point.y + dc[dir];
if (validateRange(new Point(nr, nc))) {
// santa 이동
santa1.point.setLocation(nr, nc);
return santa1;
} else {
// 최종 점수 등록
finalScore[santa1.id] = santa1.score;
// 삭제
// removeSanta.add(santa1);
santas.remove(santa1);
return null;
}
}
}
return null;
}
private static boolean isBakSal(Santa santa) {
if (!santas.contains(santa)) {
return false;
}
for (Santa santa1 : santas) {
if (santa1.isDied) {
continue;
}
if (!santa.equals(santa1) && santa.point.equals(santa1.point)) {
return true;
}
}
return false;
}
private static void collide(int dir) {
int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};
for (Santa santa : santas) {
// System.out.println(dog.point + " " + santa.point);
if (dog.point.equals(santa.point)) {
// santa 점수 증가
santa.score += C;
// santa 기절
santa.isStunned = true;
santa.whenNotStunned = 1;
// santa 이동
Point point = santa.point;
int nr = point.x + dr[dir] * C;
int nc = point.y + dc[dir] * C;
if (validateRange(new Point(nr, nc))) {
// santa 이동
santa.point.setLocation(nr, nc);
} else {
// 최종 점수 등록
finalScore[santa.id] = santa.score;
// 삭제
santa.isDied = true;
santas.remove(santa);
}
return;
}
}
}
private static boolean isCollied() {
for (Santa santa : santas) {
if (dog.point.equals(santa.point)) {
return true;
}
}
return false;
}
private static int move(Santa santa) {
int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
int minDis = Integer.MAX_VALUE;
int dir = -1;
for (int i = 0; i < 8; i++) {
int nr = dog.point.x + dx[i];
int nc = dog.point.y + dy[i];
if (!(validateRange(new Point(nr, nc)))) {
continue;
}
int dr = santa.point.x - nr;
int dc = santa.point.y - nc;
int dis = (int)(Math.pow(dr, 2) + Math.pow(dc, 2));
if (dis < minDis) {
minDis = dis;
dir = i;
}
}
int nr = dog.point.x + dx[dir];
int nc = dog.point.y + dy[dir];
dog.point.x = nr;
dog.point.y = nc;
// System.out.println("dir = " + dir);
// System.out.println(dog.point);
return dir;
}
private static Santa findSanta() {
int minDis = Integer.MAX_VALUE;
Santa temp = null;
for (Santa santa : santas) {
int dr = dog.point.x - santa.point.x;
int dc = dog.point.y - santa.point.y;
int dis = (int)(Math.pow(dr, 2) + Math.pow(dc, 2));
if (minDis > dis) {
minDis = dis;
temp = santa;
} else if (minDis == dis) {
if (temp.point.x == santa.point.x) {
temp = temp.point.y > santa.point.y ? temp : santa;
} else {
temp = temp.point.x > santa.point.x ? temp : santa;
}
}
}
// System.out.println("temp = " + temp);
return temp;
}
private static boolean validateRange(Point point) {
int r = point.x;
int c = point.y;
if (0 <= r && r < N && 0 <= c && c < N) {
return true;
}
return false;
}
}
나의 풀이
- 빡구현 문제
- 어렵긴 한데 함수를 많이 나누니까 디버깅이 편리한 건 맞는 듯하다.
- 산타가 움직일 때 죽은 산타도 충돌에 고려해주어서 틀렸었다.
- 더 쉽게 짤 수 있는 방법을 고민해보고 설계하자.
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘][X] 나무 타이쿤 (0) | 2024.03.25 |
---|---|
[알고리즘] 코드트리 오카마세 (0) | 2024.03.25 |
[알고리즘] 2048 (0) | 2024.03.22 |
[알고리즘] 미로 타워 디펜스 (0) | 2024.03.21 |
[알고리즘] 바이러스 검사 (0) | 2024.03.20 |