[골드3] 17135. 캐슬 디펜스(Java)

https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

멘탈 디펜스 실패,,

---

※  문제를 요약하면 아래와 같습니다.

▶ NxM 크기의 맵이 주어지며, 0은 적이 없음을, 1은 벽이 있음을 표시

▶ 궁수는 총 3명으로 0~M-1 까지의 Column(열) 위치 중 3 곳에서 성을 방어하며 N행에 위치

▶ 궁수 3명의 공격이 끝났을 경우 한 턴 종료

▶ 궁수는 각 턴에, 거리 D안의 적을 공격할 수 있으며 한 턴마다 가장 가까우면서 왼쪽에 있는 공격을 무조건 공격

▶ 이 때 한 턴에 중복된 적이 공격 당할 수 있음

▶ 거리 D = (r1, c1), (r2, c2) => |r1-r2| + |c1-c2|

▶ 한 턴이 종료되면 적들은 아래로 한 칸씩 이동, 성이 있는 칸으로 이동하면 (0~N-1칸을 벗어나면) 공격 불가 

▶ Input : 첫 번째 줄에 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 입력, N개의 줄에 맵 정보 입력

▶ Output : 궁수가 공격으로 제거 할 수 있는 적의 최대 수 출력

---

◈ Input - 1

5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1

◈ Output - 1

3

◈ Input - 2

5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0

◈ Output - 2

3

◈ Input - 3

5 5 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0

◈ Output - 3

5

◈ Input - 4

5 5 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

◈ Output - 4

15

◈ Input - 5

6 5 1
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0

◈ Output - 5

9

◈ Input - 6

6 5 2
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0

◈ Output - 6

14

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 궁수는 0~M-1 중 3가지 배치 가능 == 0~M-1 중 3가지를 뽑는 경우의 수 전부 탐색

▶ 재귀 형태로 중복 되지 않게 궁수의 열(Column) 위치를 3개 뽑아 탐색 진행

     ex) 0, 1, 4 나 4, 1, 0 이나 궁수가 배치되는건 동일

▶ 적들이 한 칸씩 내려간다 == 궁수가 한칸씩 올라간다와 동일 로직 표현 가능

▶ 궁수의 Col 위치는 고정 Row를 한칸씩 올리면서 (한 턴이 끝날 때 마다 Row-1 을 진행하면서) 적을 탐색

▶ 현재 궁수 3명의 위치에서 거리 D 이내의 가장 가까운 적을 찾기 위해 BFS탐색 진행

▶ BFS 방향은 궁수의 공격 가능 방향 서, 북, 동쪽을 델타 탐색 형태로 비교 공격 했을 경우 좌표 저장

▶ 궁수 3명의 공격이 끝난 후 공격한 좌표를 pAttack배열에 저장하여 중복되지 않게 카운트

▶ Row가 0이 될 때까지 탐색 반복

▶ 궁수 배치가 가능한 모든 경우의 수를 탐색하여 최대로 제거가능한 적의 수 출력

---

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

class Point {
	int m_nRow;
	int m_nCol;
	int m_nDistance;

	public Point(int m_nRow, int m_nCol, int m_nDistance) {
		this.m_nRow = m_nRow;
		this.m_nCol = m_nCol;
		this.m_nDistance = m_nDistance;
	}

}

public class Main {
	static boolean[][] barrVisited;
	static boolean[][] barrAttacked;
	static boolean[][] barrMap;
	static int N, M, D, nResult, nMax, nArcherIndex;
	static int[] arrArcher;
	static boolean[] barrArcVisit;

	// 서, 북, 동
	static int[] dr = { 0, -1, 0 };
	static int[] dc = { -1, 0, 1 };
	static Point[] pAttack = new Point[3];
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(bReader.readLine());

		N = Integer.parseInt(st.nextToken()); // Row
		M = Integer.parseInt(st.nextToken()); // Col
		D = Integer.parseInt(st.nextToken()); // Distance

		barrMap = new boolean[N][M];
		arrArcher = new int[3];
		barrArcVisit = new boolean[M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bReader.readLine());
			for (int j = 0; j < M; j++) {
				if (Integer.parseInt(st.nextToken()) == 1) {
					barrMap[i][j] = true;
				}
			}
		}
		// 궁수 번호 뽑자
		// 조합
		nMax = 0;
		ArcherNum(0);

		bWriter.write(String.valueOf(nMax));
		bWriter.close();
	}

	// 궁수 배치의 경우의 수
	// 이놈의 경우의 수
	private static void ArcherNum(int nIndex) {
		// 기저 조건
		if (nIndex == 3) {
			// System.out.println(Arrays.toString(arrArcher));
			// 각 궁수의 위치를 표현
			barrVisited = new boolean[N][M];
			barrAttacked = new boolean[N][M];
			nResult = 0;
			// 탐색합시다
			int nRow = N - 1;
			while (nRow >= 0) {
				// 궁수는 가장 가까운 왼쪽만 무조건 공격인듯 ??
				// 각각의 궁수 Col 위치의
				// N-1~0까지 D거리안의 가장 가까운 왼쪽 적을 탐색
				for (int i = 0; i < 3; i++) {
					pAttack[i] = new Point(-1,-1,0);
					nArcherIndex = i;
					BFS(new Point(nRow, arrArcher[i], 0));
				}
				nRow--;
				// 위의 한 턴 (궁수 3명의 공격)에서 공격한 좌표를 불러와서
				// 공격한 Row, Col 좌표를 저장
				for(int i =0; i < 3; i++) {
					int nEnemyRow = pAttack[i].m_nRow;
					int nEnemyCol = pAttack[i].m_nCol;
					
					// 궁수가 적이 없었거나 이미 공격했다고 카운트했으면 넘어가자
					if(nEnemyRow == -1 || barrAttacked[nEnemyRow][nEnemyCol])
						continue;
					
					barrAttacked[nEnemyRow][nEnemyCol] = true;
					nResult++;
				}
			}
			
			if(nMax < nResult)
				nMax = nResult;
			return;
		}

		// 재귀 조건
		// 0, 1, 2나
		// 2, 1, 0이나
		// 0 2,1 이나 궁수가 0,1,2 세위치에 배치되있는건 똑같자나??
		// 첫 배열값 아니면 이전 배열값 부터 시작해
		// 그니까 중복제거!
		int nArrNum = nIndex;
		if (nIndex != 0)
			nArrNum--;

		// 돌립시다
		for (int i = arrArcher[nArrNum]; i < M; i++) {
			if (!barrArcVisit[i]) {
				arrArcher[nIndex] = i;
				barrArcVisit[i] = true;
				ArcherNum(nIndex + 1);
				barrArcVisit[i] = false;
			}
		}

	}

	private static void BFS(Point Archer) {
		Queue<Point> queueBFS = new LinkedList<>();
		
		queueBFS.add(Archer);

		while (!queueBFS.isEmpty()) {
			// 적이 있다면 공격해버리고 포인트 저장!
			Point p = queueBFS.poll();
		
			// 거리가 D가 넘거나
			// 공격을 이미 했거나
			// bfs 방문했으면 넘어가버려
			if(barrVisited[p.m_nRow][p.m_nCol] || p.m_nDistance >= D)
				continue;
		
			// 이전 턴들에서 공격한 포인트가 아닌데 적이 존재하면 해당 좌표 저장
			// 가장 가까운 공격 포인트 찾으면 되니까 리턴
			if(barrMap[p.m_nRow][p.m_nCol] && !barrAttacked[p.m_nRow][p.m_nCol]) {
				pAttack[nArcherIndex] = p;
				return;
			}
			
			// 무조건 왼쪽 먼저
			for(int i = 0; i < dr.length; i++) {
				int nSearchRow = p.m_nRow + dr[i];
				int nSearchCol = p.m_nCol + dc[i];
				
				if(nSearchRow < 0 || nSearchCol < 0 || nSearchRow >= N || nSearchCol >= M)
					continue;
				
				queueBFS.add(new Point(nSearchRow, nSearchCol, p.m_nDistance + 1));
			}
		}
	}

}

---

Good 추석 연휴! (피드백 감사합니다!)