[코드트리] 포탑 부수기 JAVA 풀이 (삼성 SW 역량 기출문제)

https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/description?page=3&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

bfs를 사용하여 문제를 풀 수 있었다.

최단거리의 경로를 알기위해 come배열에 어떤 곳에서 출발하여 온 것인지 표시하여

목적지부터 역순으로 come배열을 조회하여 출발지에 도착할 수 있도록 하는 게 포인트였다!

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int n, m, k, time = 1;
	static int[][] map;
	static int[][] tempMap;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };
	static int[][] attackerList;

	static class Node {
		int x, y;

		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	static class Top {
		int x, y, power;

		Top(int x, int y, int power) {
			this.x = x;
			this.y = y;
			this.power = power;
		}
	}

	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());

		map = new int[n][m];
		tempMap = new int[n][m];
		attackerList = new int[n][m];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		while (time < k + 1) {

			for(int i=0;i<n;i++) {
				tempMap[i]=map[i].clone();
			}

			Top attacker = getAttacker();
			Top strongTop = getStrongTop();

			map[strongTop.x][strongTop.y] -= attacker.power;

			if (!attack1(attacker, strongTop)) {
				attack2(attacker, strongTop);
			}

			plus(attacker, strongTop);

			if (checkTopCount() == 1)
				break;
			time++;
		}

		int max = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				max = Math.max(map[i][j], max);
			}
		}
		System.out.println(max);
	}

	static void plus(Top a, Top b) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (tempMap[i][j] == map[i][j]&&map[i][j]>0&&(i!=a.x&&j!=a.y))
					map[i][j] += 1;
			}
		}
	}

	static void attack2(Top a, Top b) {
		int[] dx2 = { 0, 0, 1, -1, 1, -1, 1, -1 };
		int[] dy2 = { 1, -1, 0, 0, 1, 1, -1, -1 };
		for (int i = 0; i < 8; i++) {
			int xx = (b.x + dx2[i] + n) % n;
			int yy = (b.y + dy2[i] + m) % m;

			if (xx == a.x && yy == a.y)
				continue;

			if (map[xx][yy] <= 0)
				continue;
			map[xx][yy] -= (a.power / 2);
		}
	}

	static boolean attack1(Top a, Top b) {
		Queue<Top> q = new LinkedList<>();
		q.add(a);
		Node[][] come = new Node[n][m];
		boolean[][] visited = new boolean[n][m];
		visited[a.x][a.y] = true;

		while (!q.isEmpty()) {
			Top t = q.poll();
			for (int i = 0; i < 4; i++) {
				int xx = t.x + dx[i];
				int yy = t.y + dy[i];

				if (xx < 0 || yy < 0 || xx >= n || yy >= m || visited[xx][yy] || map[xx][yy] <= 0)
					continue;

				come[xx][yy] = new Node(t.x, t.y);
				q.add(new Top(xx, yy, map[xx][yy]));
				visited[xx][yy] = true;
			}
		}

		if (come[b.x][b.y] == null) {
			return false;
		}

		Node node = come[b.x][b.y];
		int xx = node.x;
		int yy = node.y;
		while (true) {
			if(xx == a.x && yy == a.y) break;
			map[xx][yy] -= a.power / 2;
			Node tempN=come[xx][yy];
			xx = tempN.x;
			yy = tempN.y;
		}
		return true;
	}


	static Top getStrongTop() {
		int maxPower = Integer.MIN_VALUE;
		int maxx = 0;
		int maxy = 0;
		int minTurn = Integer.MAX_VALUE;
		for (int sum = 0; sum<= n + m - 2; sum++) {
			for (int j = 0; j < m; j++) {
				int i = sum - j;

				if (i < 0 || i >= n)
					continue;
				if (map[i][j] > 0) {
					if (maxPower < map[i][j]) {
						maxPower = map[i][j];
						maxx = i;
						maxy = j;
						minTurn = attackerList[i][j];
					} else if (maxPower == map[i][j] && minTurn > attackerList[i][j]) {
						maxPower = map[i][j];
						maxx = i;
						maxy = j;
						minTurn = attackerList[i][j];
					}
				}
			}
		}
		return new Top(maxx, maxy, map[maxx][maxy]);
	}

	static Top getAttacker() {
		int minPower = Integer.MAX_VALUE;
		int minx = 0;
		int miny = 0;
		int maxTurn = 0;
		for (int sum = n + m - 2; sum >= 0; sum--) {
			for (int j = m - 1; j >= 0; j--) {
				int i = sum - j;

				if (i < 0 || i >= n)
					continue;
				if (map[i][j] > 0) {
					if (minPower > map[i][j]) {
						minPower = map[i][j];
						minx = i;
						miny = j;
						maxTurn = attackerList[i][j];
					} else if (minPower == map[i][j] && maxTurn < attackerList[i][j]) {
						minPower = map[i][j];
						minx = i;
						miny = j;
						maxTurn = attackerList[i][j];
					}
				}
			}
		}
		attackerList[minx][miny] = time;
		map[minx][miny] += n + m;
		return new Top(minx, miny, map[minx][miny]);
	}

	static int checkTopCount() {
		int count = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] > 0) {
					count++;
				}
			}
		}
		return count;
	}
}