[백준] 17135 캐슬 디펜스 - 깊이우선탐색(DFS) + 조합(Combination) + 너비우선탐색(BFS) JAVA

passionfruit200 2023. 11. 9. 17:34

2023. 11. 9. 17:34

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

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

passionfruit200