https://www.acmicpc.net/problem/17135
17135번: 캐슬 디펜스
첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.
www.acmicpc.net
코드설명
조합과 너비우선탐색(BFS)와 구현 문제입니다.
문제 로직입니다.
- 1. 조합 생성
- 재귀적 백트래킹 접근 방식을 사용하여 세 명의 궁수의 모든 가능한 조합을 생성합니다. getComb 함수는 선택된 궁수에 대해 hunter[i]를 true로 설정하고 다른 경우에는 false로 설정하여 이러한 조합을 생성합니다.
- 2. BFS (너비 우선 탐색)
- BFS 함수는 궁수의 방어 과정을 시뮬레이션하기 위해 사용됩니다. 이 함수는 각 선택된 궁수의 위치에서 너비 우선 탐색을 수행하고 주어진 공격 범위 D 내에서 가장 가까운 몬스터를 찾습니다. 유효한 대상을 찾으면 이를 huntList에 추가합니다. 그런 다음, 잡힌 몬스터들은 맵에서 제거되고 남은 몬스터들은 한 칸 아래로 이동합니다.
- 3. 몬스터 제거 및 맵 업데이트를 합니다.
- getDown 함수는 몬스터들을 한 칸 아래로 이동시킵니다. 각 열의 요소를 아래로 이동시키고 맨 위의 행을 0으로 설정합니다.
문제에서 실수했었던점은,
ArrayList huntList를 한턴의 캐슬디펜스 한턴이 끝난 후 새로 선언하지 않았다는 점입니다.
그렇게 하지 않을경우, ArrayList에 사냥할 목록이 남아있어 다음턴에 몬스터들이 한 칸 내려온 이후에도 작동하여 올바르게 COunting하지 않습니다.
while(moveCnt <= N) {
moveCnt += 1;
ArrayList<Node> huntList = new ArrayList<Node>();
...
...
...
}
두번쨰 실수점 또한, Queue의 초기화를 올바르게 진행하지 않았다는 점입니다.
아래와 같이 궁수를 찾고 궁수가 사냥을 시작할때면 항상 새로 시작하여 이전 궁수의 Queue 값이 남아있지 않도록 해야합니다.
for(int i=0;i<M;i++) {
if(hunter[i] == true) {
Queue<Node> q = new LinkedList<>();
hunterVisited = new boolean[N+1][M];
q.offer(new Node(N, i, 0));
hunterVisited[N][i] = true;
while(!q.isEmpty()) {
세번쨰는, 궁수가 같은 곳을 사냥할 수 있다는 점입니다.
해당사항은 alreadyEaten[][] 배열을 통해서 alreadyEaten[][]에 도달할경우 해당 칸 또한 먹을 수 있도록 해결하거나, huntList 배열을 추가하여 사냥감 목록을 넣고 실제 map은 마지막에 0 으로 갱신하는 방법이 있습니다.
단순함만을 생각한다면 huntList를 통해서 동기화 시키는 것이 낫겠지만, 속도의 경우 alreadyEaten[][]을 통해 처리하는것이 빠릅니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int T, N, M, D;
public static int[][] map;
public static int[][] copyMap;
public static boolean[] hunter;
public static boolean[][] hunterVisited;
public static int answer = 0;
public static int huntCnt = 0;
public static int[] dx = {0,-1,1,0}; //왼쪽, 상, 하, 우
public static int[] dy = {-1, 0, 0, 1};
public static StringBuilder sb = new StringBuilder();
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());
D = Integer.parseInt(st.nextToken());
map = new int[N+1][M];
hunter = new boolean[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());
}
}
getComb(0, 0);
System.out.println(answer);
}
public static void getComb(int level, int idx) {
if(level == 3) {
BFS();
answer = Math.max(answer, huntCnt);
return ;
}
for(int i=idx;i<M;i++) {
hunter[i] = true;
getComb(level + 1, i + 1);
hunter[i] = false;
}
}
public static void BFS() {
hunterVisited = new boolean[N+1][M];
copyMap = new int[N+1][M];
for(int i=0;i<N+1;i++) {
for(int j=0;j<M;j++) {
copyMap[i][j] = map[i][j];
}
}
int moveCnt = 0;
huntCnt = 0;
while(moveCnt <= N) {
moveCnt += 1;
ArrayList<Node> huntList = new ArrayList<Node>();
for(int i=0;i<M;i++) {
if(hunter[i] == true) {
Queue<Node> q = new LinkedList<>();
hunterVisited = new boolean[N+1][M];
q.offer(new Node(N, i, 0));
hunterVisited[N][i] = true;
while(!q.isEmpty()) {
Node temp = q.poll();
if(copyMap[temp.r][temp.c] == 1) { //잡았다면 정답에 넣는다.
huntList.add(new Node(temp.r, temp.c, 0));
break;
}
for(int dir=0;dir<4;dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if(hunterVisited[nr][nc] == false && temp.cnt + 1 <= D) {
q.offer(new Node(nr, nc, temp.cnt + 1));
hunterVisited[nr][nc] = true;
}
}
}
}
}
//사냥한것 위치 0 으로 갱신
for(int i=0;i<huntList.size();i++) {
Node temp = huntList.get(i);
if(copyMap[temp.r][temp.c] == 1) {
// System.out.println("delete "+ "tempR:"+temp.r+" tempC:"+temp.c);
copyMap[temp.r][temp.c] = 0;
huntCnt += 1;
}
}
getDown();
}
}
public static void getDown() {
for(int i=0;i<M;i++) {
for(int j=N-1;j>=1;j--) {
copyMap[j][i] = copyMap[j-1][i];
}
copyMap[0][i] = 0;
}
}
}
class Node{
int r;
int c;
int cnt;
public Node(int r, int c, int cnt) {
this.r=r;
this.c=c;
this.cnt = cnt;
}
}
사냥꾼이 따로따로 사냥하도록 BFS를 진행했습니다.
이렇게 진행할경우 동시에 같은 사냥감을 먹어도 상관없도록 alreadyEaten[][] , 즉 이미 먹혔을 경우에도 작동하도록 조건을 추가해주어야합니다.
바로 상단의 코드에서는 사냥목록을 huntList에 넣어두고서 처리하고, 마지막에 huntList에 위치한 사냥감들을 0으로 초기화시켜줍니다.
속도적인 면에서는 아래의 코드가 빠릅니다.
package algorhythm;
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 {
public static int N, M, D;
public static int[][] map;
public static int[][] storeMap;
public static boolean[] visited;
public static boolean[][] alreadyEaten;
public static int answer = 0;
public static int archor = 99;
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());
D = Integer.parseInt(st.nextToken());
map = new int[N+1][M];
storeMap = new int[N+1][M];
visited = new boolean[M];
alreadyEaten = new boolean[N+1][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());
}
}
simulate(0, 0);
System.out.println(answer);
}
public static void simulate(int level, int idx) {
if(level == 3) {
for(int i=0;i<=N;i++) {
for(int j=0;j<M;j++) {
storeMap[i][j] = map[i][j];
}
}
int huntCnt = 0;
int turn = 0;
while(turn++ <= N) {
alreadyEaten = new boolean[N+1][M];
for(int i=0;i<M;i++) {
if(map[N][i] == archor) {
huntCnt += protectBFS(i);
}
}
slideDown();
}
answer = Math.max(answer, huntCnt);
return ;
}
for(int i=idx;i<M;i++) {
if(visited[i] == false) {
visited[i] = true;
map[N][i] = archor;
simulate(level + 1, i + 1);
map[N][i] = 0;
visited[i] = false;
}
}
}
public static int protectBFS(int c) {
//좌, 상, 우
int[] dx = {0, -1, 0};
int[] dy = {-1, 0, 1};
int huntCnt = 0;
Queue<Node> q = new LinkedList<Node>();
q.offer(new Node(N, c, 0));
boolean[][] visited = new boolean[N+1][M];
visited[N][c] = true;
while(!q.isEmpty()) {
Node temp = q.poll();
if(temp.distance >= D) { // >=D 인 이유는 0번쨰 시작에서 다음것을 검사하는 순간 1 번째 거리를 검사하는 것이기 떄문입니다.
break;
}
for(int dir = 0; dir < 3; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if(visited[nr][nc] == true) continue;
if(storeMap[nr][nc] > 0 || alreadyEaten[nr][nc] == true) {
huntCnt = storeMap[nr][nc];
//이미 먹혔다면 딱 한번만 더해줘야할 것 이다.
//해당 부분을 이미 먹혔다는 true값으로 바꿔준다.
//다음 헌터가 해당 부분을 마주한다면, 이미 true인 상태이므로 return 0을 통해 아무것도 먹지 못한다.
//이미 먹힌것을 확인하는 방법은 boolean[][] 배열을 따로 하나 만들어서 전역적으로 관리한다.
if(alreadyEaten[nr][nc] == true) {
return 0;
}
alreadyEaten[nr][nc] = true;
storeMap[nr][nc] = 0;
return huntCnt;
}
visited[nr][nc] = true;
q.offer(new Node(nr, nc, temp.distance + 1));
}
}
return huntCnt;
}
public static void slideDown() {
for(int col =0; col<M;col++) {
for(int row = N - 1; row > 0; row--) {
storeMap[row][col] = storeMap[row - 1][col];
}
storeMap[0][col] = 0;
}
}
}
class Node{
int r;
int c;
int distance = 0;
public Node(int r, int c, int distance) {
this.r=r;
this.c=c;
this.distance = distance;
}
}
사냥꾼의 위치를 DFS로 완전탐색하는 코드입니다.
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 {
public static int N, M, D;
public static int[][] map;
public static int[][] storeMap;
public static boolean[] visited;
public static boolean[][] alreadyEaten;
public static int answer = 0;
public static int archor = 99;
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());
D = Integer.parseInt(st.nextToken());
map = new int[N+1][M];
storeMap = new int[N+1][M];
visited = new boolean[M];
alreadyEaten = new boolean[N+1][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());
}
}
simulate(0, 0);
System.out.println(answer);
}
public static void simulate(int level, int selected) {
if(selected == 3) {
for(int i=0;i<=N;i++) {
for(int j=0;j<M;j++) {
storeMap[i][j] = map[i][j];
}
}
int huntCnt = 0;
int turn = 0;
while(turn++ <= N) {
alreadyEaten = new boolean[N+1][M];
for(int i=0;i<M;i++) {
if(map[N][i] == archor) {
huntCnt += protectBFS(i);
}
}
slideDown();
}
answer = Math.max(answer, huntCnt);
return ;
}
if(level == M) {
return ;
}
if(map[N][level] == 0) {
map[N][level] = archor;
simulate(level + 1, selected + 1);
map[N][level] = 0;
}
simulate(level + 1, selected);
}
public static int protectBFS(int c) {
//좌, 상, 우
int[] dx = {0, -1, 0};
int[] dy = {-1, 0, 1};
int huntCnt = 0;
Queue<Node> q = new LinkedList<Node>();
q.offer(new Node(N, c, 0));
boolean[][] visited = new boolean[N+1][M];
visited[N][c] = true;
while(!q.isEmpty()) {
Node temp = q.poll();
if(temp.distance >= D) { // >=D 인 이유는 0번쨰 시작에서 다음것을 검사하는 순간 1 번째 거리를 검사하는 것이기 떄문입니다.
break;
}
for(int dir = 0; dir < 3; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if(visited[nr][nc] == true) continue;
if(storeMap[nr][nc] > 0 || alreadyEaten[nr][nc] == true) {
huntCnt = storeMap[nr][nc];
//이미 먹혔다면 딱 한번만 더해줘야할 것 이다.
//해당 부분을 이미 먹혔다는 true값으로 바꿔준다.
//다음 헌터가 해당 부분을 마주한다면, 이미 true인 상태이므로 return 0을 통해 아무것도 먹지 못한다.
//이미 먹힌것을 확인하는 방법은 boolean[][] 배열을 따로 하나 만들어서 전역적으로 관리한다.
if(alreadyEaten[nr][nc] == true) {
return 0;
}
alreadyEaten[nr][nc] = true;
storeMap[nr][nc] = 0;
return huntCnt;
}
visited[nr][nc] = true;
q.offer(new Node(nr, nc, temp.distance + 1));
}
}
return huntCnt;
}
public static void slideDown() {
for(int col =0; col<M;col++) {
for(int row = N - 1; row > 0; row--) {
storeMap[row][col] = storeMap[row - 1][col];
}
storeMap[0][col] = 0;
}
}
}
class Node{
int r;
int c;
int distance = 0;
public Node(int r, int c, int distance) {
this.r=r;
this.c=c;
this.distance = distance;
}
}
처음에 올바르게 초기화 시키지 않고, 약간의 조건 누락
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int T, N, M, D;
public static int[][] map;
public static int[][] copyMap;
public static boolean[] hunter;
public static boolean[][] hunterVisited;
public static int answer = 0;
public static int huntCnt = 0;
public static int[] dx = {0,-1,1,0}; //왼쪽, 상, 하, 우
public static int[] dy = {-1, 0, 0, 1};
public static StringBuilder sb = new StringBuilder();
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());
D = Integer.parseInt(st.nextToken());
map = new int[N+1][M];
hunter = new boolean[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());
}
}
getComb(0, 0);
System.out.println(answer);
}
public static void getComb(int level, int idx) {
if(level == 3) {
BFS();
answer = Math.max(answer, huntCnt);
return ;
}
for(int i=idx;i<M;i++) {
hunter[i] = true;
getComb(level + 1, i + 1);
hunter[i] = false;
}
}
public static void BFS() {
Queue<Node> q = new LinkedList<>();
ArrayList<Node> huntList = new ArrayList<Node>();
hunterVisited = new boolean[N+1][M];
copyMap = new int[N+1][M];
for(int i=0;i<N+1;i++) {
for(int j=0;j<M;j++) {
copyMap[i][j] = map[i][j];
}
}
int moveCnt = 0;
huntCnt = 0;
while(moveCnt <= N) {
moveCnt += 1;
for(int i=0;i<M;i++) {
if(hunter[i] == true) {
hunterVisited = new boolean[N+1][M];
q.offer(new Node(N, i, 0));
hunterVisited[N][i] = true;
while(!q.isEmpty()) {
Node temp = q.poll();
if(copyMap[temp.r][temp.c] == 1) { //잡았다면 정답에 넣는다.
huntList.add(new Node(temp.r, temp.c, 0));
break;
}
for(int dir=0;dir<4;dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if(hunterVisited[nr][nc] == false && temp.cnt + 1 <= D) {
q.offer(new Node(nr, nc, temp.cnt + 1));
hunterVisited[nr][nc] = true;
}
}
}
}
}
//사냥한것 위치 0 으로 갱신
for(int i=0;i<huntList.size();i++) {
Node temp = huntList.get(i);
if(copyMap[temp.r][temp.c] == 1) {
copyMap[temp.r][temp.c] = 0;
huntCnt += 1;
}
}
getDown();
}
}
public static void getDown() {
for(int i=0;i<M;i++) {
for(int j=N-1;j>=1;j--) {
copyMap[j][i] = copyMap[j-1][i];
}
copyMap[0][i] = 0;
}
}
}
class Node{
int r;
int c;
int cnt;
public Node(int r, int c, int cnt) {
this.r=r;
this.c=c;
this.cnt = cnt;
}
}'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 1726 로봇 - 너비우선탐색(BFS) JAVA (0) | 2023.11.10 |
|---|---|
| [백준] 17142 연구소 3 - 조합(Combination) + 너비우선탐색(BFS) + DFS(깊이우선탐색) JAVA (0) | 2023.11.09 |
| [백준] 1941 소문난 칠공주 - 조합(Combination) + BFS(너비우선탐색) JAVA (0) | 2023.11.09 |
| [백준] 1516 게임 개발 - DP + 위상 정렬(Topology Sort) JAVA (0) | 2023.11.09 |
| [백준] 1937 욕심쟁이 판다 - DP + 깊이우선탐색(DFS) JAVA (0) | 2023.11.08 |