알고리즘 풀이/Java
[알고리즘][X] 왕실의 기사 대결
Dong's Universe
2024. 3. 26. 21:27
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main2 {
static final int MAX_N = 31;
static final int MAX_L = 41;
static int l, n, q;
static int[][] info = new int[MAX_L][MAX_L];
static int[] bef_k = new int[MAX_N];
static int[] r = new int[MAX_N], c = new int[MAX_N], h = new int[MAX_N], w = new int[MAX_N], k = new int[MAX_N];
static int[] nr = new int[MAX_N], nc = new int[MAX_N];
static int[] dmg = new int[MAX_N];
static boolean[] is_moved = new boolean[MAX_N];
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
static boolean tryMovement(int idx, int dir) {
Queue<Integer> q = new ArrayDeque<>();
boolean is_pos = true;
for (int i = 1; i <= n; i++) {
dmg[i] = 0;
is_moved[i] = false;
nr[i] = r[i];
nc[i] = c[i];
}
q.add(idx);
is_moved[idx] = true;
while (!q.isEmpty()) {
int x = q.poll();
nr[x] += dx[dir];
nc[x] += dy[dir];
if (nr[x] < 1 || nc[x] < 1 || nr[x] + h[x] - 1 > l || nc[x] + w[x] - 1 > l) {
return false;
}
for (int i = nr[x]; i <= nr[x] + h[x] - 1; i++) {
for (int j = nc[x]; j <= nc[x] + w[x] - 1; j++) {
if (info[i][j] == 1) {
dmg[x]++;
}
if (info[i][j] == 2) {
return false;
}
}
}
for (int i = 1; i <= n; i++) {
if (is_moved[i] || k[i] <= 0) {
continue;
}
if (r[i] > nr[x] + h[x] - 1 || nr[x] > r[i] + h[i] - 1) {
continue;
}
if (c[i] > nc[x] + w[x] - 1 || nc[x] > c[i] + w[i] - 1) {
continue;
}
is_moved[i] = true;
q.add(i);
}
}
dmg[idx] = 0;
return true;
}
static void movePiece(int idx, int dir) {
if (k[idx] <= 0) {
return;
}
if (tryMovement(idx, dir)) {
for (int i = 1; i <= n; i++) {
r[i] = nr[i];
c[i] = nc[i];
k[i] -= dmg[i];
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
l = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
q = Integer.parseInt(st.nextToken());
for (int i = 1; i <= l; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= l; j++) {
info[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
r[i] = Integer.parseInt(st.nextToken());
c[i] = Integer.parseInt(st.nextToken());
h[i] = Integer.parseInt(st.nextToken());
w[i] = Integer.parseInt(st.nextToken());
k[i] = Integer.parseInt(st.nextToken());
bef_k[i] = k[i];
}
for (int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
int idx = Integer.parseInt(st.nextToken());
int dir = Integer.parseInt(st.nextToken());
movePiece(idx, dir);
}
int result = 0;
for (int i = 1; i <= n; i++) {
if (k[i] <= 0) {
continue;
}
result += bef_k[i] - k[i];
}
System.out.println(result);
}
}참고해서 푼 풀이
- 연쇄 작용 =. queue를 활용
- 배열에 상태들을 저장. 인덱스는 키
- 해설을 보니까 시야를 넓히는데 도움이 많이 된다.
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static class Knight{
int id;
Point point;
final Point size;
int hp;
int damage;
public Knight(int id, Point point, Point size, int hp) {
super();
this.id = id;
this.point = point;
this.size = size;
this.hp = hp;
this.damage = 0;
}
public Knight(Knight knight) {
super();
this.id = knight.id;
this.point = knight.point;
this.size = knight.size;
this.hp = knight.hp;
this.damage = knight.damage;
}
@Override
public String toString() {
return "Knight [id=" + id + ", point=" + point + ", size=" + size + ", hp=" + hp + ", damage=" + damage
+ "]";
}
}
static HashMap<Integer, Knight> knights;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static boolean flag;
static int[][] map;
static int[][] knightMap;
static List<Integer> willDamage;
static int L;
static int N;
static int Q;
static int sum;
static int[][] newKnightMap;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
L = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());
sum = 0;
knights = new HashMap<>();
knightMap = new int[L+1][L+1];
newKnightMap = new int[L+1][L+1];
willDamage = new ArrayList<>();
map = new int[L+1][L+1];
for (int i = 1; i <= L; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= L; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
Point point = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
Point size = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
int hp = Integer.parseInt(st.nextToken());
Knight knight = new Knight(i, point, size, hp);
knights.put(i, knight);
for (int j = 0; j < size.x; j++) {
for (int k = 0; k < size.y; k++) {
knightMap[j+point.x][k+point.y] = i;
}
}
}
for (int i = 0; i < Q; i++) {
st = new StringTokenizer(br.readLine());
int id = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
if (!knights.containsKey(id)) {
continue;
}
playGame(id, d);
System.out.println(i+1);
print();
}
for (Knight knight : knights.values()) {
sum += knight.damage;
}
// print();
// System.out.println(findPoints(1));
// System.out.println(findKnight(1, 0));
//
System.out.println(knights.values());
System.out.println(sum);
}
private static void print() {
for (int i = 1; i <= L; i++) {
for (int j = 1; j <= L; j++) {
System.out.print(knightMap[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
private static void playGame(int id, int d) {
flag = true;
// System.out.println("id1 " + id);
validateMove(id, d);
System.out.println(flag);
if (flag) {
newKnightMap = new int[L+1][L+1];
for (int i = 1; i <= L; i++) {
for (int j = 1; j <= L; j++) {
newKnightMap[i][j] = knightMap[i][j];
}
}
willDamage = new ArrayList<>();
move(id, d);
// for (int i = 1; i <= L; i++) {
// for (int j = 1; j <= L; j++) {
// knightMap[i][j] = newKnightMap[i][j];
// }
// }
update(id, d);
knightMap = newKnightMap;
damage(id);
}
}
private static void update(int id, int d) {
List<Point> points = findPoints(id);
Knight knight = knights.get(id);
Point fPoint = points.get(0);
knight.point = new Point(fPoint.x + dx[d], fPoint.y + dy[d]);
for (Integer i : willDamage) {
points = findPoints(i);
knight = knights.get(i);
fPoint = points.get(0);
knight.point = new Point(fPoint.x + dx[d], fPoint.y + dy[d]);
}
}
private static void move(int id, int d) {
List<Point> points = findPoints(id);
Knight knight = knights.get(id);
for (Point point : points) {
if (newKnightMap[point.x][point.y] == id) {
newKnightMap[point.x][point.y] = 0;
}
}
for (Point point : points) {
int nx = point.x + dx[d];
int ny = point.y + dy[d];
// knightMap[nx][ny] = id;
newKnightMap[nx][ny] = id;
}
List<Knight> finds = findKnight(id, d);
for (Knight knigh : finds) {
move(knigh.id, d);
willDamage.add(knigh.id);
}
// Point fPoint = points.get(0);
// knight.point = new Point(fPoint.x + dx[d], fPoint.y + dy[d]);
}
private static void damage(int id) {
for (int i = 1; i <= L; i++) {
for (int j = 1; j <= L; j++) {
if (map[i][j] == 1) {
if (knightMap[i][j] > 0 && knightMap[i][j] != id && willDamage.contains(Integer.valueOf(knightMap[i][j]))) {
Knight knight = knights.get(knightMap[i][j]);
knight.hp--;
knight.damage++;
if (knight.hp <= 0) {
List<Point> points = findPoints(knightMap[i][j]);
for (Point point : points) {
knightMap[point.x][point.y] = 0;
}
knights.remove(Integer.valueOf(knight.id));
}
}
}
}
}
}
private static boolean validateMove(int id, int d) {
List<Knight> finds = findKnight(id, d);
if (finds.isEmpty()) {
if (!judge(id, d)) {
flag = false;
return false;
}
}
for (Knight knight : finds) {
validateMove(knight.id, d);
if (!flag) {
return false;
}
}
return false;
}
private static boolean judge(int id, int d) {
List<Point> points = findPoints(id);
for (Point point : points) {
int nx = point.x + dx[d];
int ny = point.y + dy[d];
if (!rangeCheck(nx, ny) || map[nx][ny] == 2) {
return false;
}
}
return true;
}
private static List<Point> findPoints(int id) {
Knight knight = knights.get(id);
List<Point> points = new ArrayList<>();
for (int j = 0; j < knight.size.x; j++) {
for (int k = 0; k < knight.size.y; k++) {
points.add(new Point(j+knight.point.x, k+knight.point.y));
}
}
return points;
}
private static List<Knight> findKnight(int id, int d) {
List<Point> points = findPoints(id);
HashSet<Integer> set = new HashSet<>();
// List<Integer> set = new ArrayList<>();
for (Point point : points) {
int x = point.x;
int y = point.y;
int nx = x + dx[d];
int ny = y + dy[d];
if (rangeCheck(nx, ny)) {
if (knightMap[nx][ny] > 0 && knightMap[nx][ny] != id) {
set.add(knightMap[nx][ny]);
// if (!set.contains(knightMap[nx][ny])) {
// set.add(knightMap[nx][ny]);
// }
}
}
}
List<Knight> result = new ArrayList<>();
for (Integer integer : set) {
result.add(knights.get(integer));
// System.out.println("id " + id);
// System.out.println(knights.get(integer));
}
return result;
}
private static boolean rangeCheck(int x, int y) {
if (1 <= x && x <= L && 1 <= y && y <= L) {
return true;
}
return false;
}
}이건 나의 풀이
- 틀렸다. 이유는 모르겠지만 함수가 서로 엮여 있어서 그런 거 같다. 이런 식으로 짜면 안될 것이다.
- 함수 안에서 상태가 계속 바뀔 수 있는데 그 때문인 거 같다.