import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Cattle_Defense {
static int N,M,D;
static int[][] map;
static boolean[][] visited;
static int max = Integer.MIN_VALUE;
static int enemy = 0;
static int[] archerList = new int[3];
static int[] dr = {0,-1,0,1};
static int[] dc = {-1,0,1,0};
static int[][] copymap;
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];
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());
}
}
dfs(0,0);
System.out.println(max);
}
public static void dfs(int col,int cnt){
if(cnt==3){
enemy = 0;
kill();
max = Math.max(max,enemy);
return;
}
for (int i = col; i < M; i++) {
archerList[cnt] = i;
dfs(i+1, cnt + 1);
}
}
public static void kill(){
int count = 1;
copymap = new int[N+1][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copymap[i][j]=map[i][j];
}
}
while(true) {
if(count==N*M){
break;
}
count = 0;
for (int k = 0; k < 3; k++) {
Queue<int[]> que = new LinkedList<>();
//궁수 한명이 잡을 수 있는 적(enemylist에서 체크)
que.add(new int[]{N, archerList[k]});
visited = new boolean[N][M];
outloop:
while (!que.isEmpty()) {
int[] current = que.poll();
int crow = current[0];
int ccol = current[1];
for (int i = 0; i < 4; i++) {
int nrow = crow + dr[i];
int ncol = ccol + dc[i];
if (nrow < 0 || ncol < 0 || nrow >= N || ncol >= M)
continue;
if (Math.abs(N - nrow) + Math.abs(archerList[k] - ncol) > D)
continue;
if (!visited[nrow][ncol]) {
visited[nrow][ncol] = true;
que.add(new int[]{nrow, ncol});
if (copymap[nrow][ncol] == 1) {//처음쏘는 적이면 처치수 +1
enemy++;
copymap[nrow][ncol] = -1;
break outloop;
} else if (copymap[nrow][ncol] == -1) {//두번째 쏘는 적이면 처치수 계산 x
break outloop;
}
}
}
}
}
for (int i = N-1; i >=0; i--) {// 적 전진
for (int j = 0; j < M; j++) {
if(copymap[i][j]==-1){
copymap[i][j]=0;
}
else if(copymap[i][j]==1){
copymap[i+1][j]=copymap[i][j];
copymap[i][j]=0;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(copymap[i][j]==0)
count++;
}
}
}
}
}
풀이방법
- 크게보면 궁수의 위치를 N+1행에서 돌면서 조합하고(dfs) 궁수 3명의 위치를 지정했으면,
적을 없애는 함수로 넘어간다. - 적을 없애는 함수는 궁수의 위치에서 왼쪽부터 방향을 확인하는 bfs를 구현하여 적을 없애고, 맵을 이동한다.
- dfs함수를 통해 궁수 3명의 위치에 따른 경우의 수를 세고, 그에 따른 적 사살 수의 최댓값을 구한다.
📢이때 궁수의 위치는 중복이 안되므로, 내 위치 이후의 조합만을 생각한다.
for (int i = col; i < M; i++) {
archerList[cnt] = i;
dfs(i+1, cnt + 1);
}-
kill()함수 실행시 map을 변경하면, 다음 경우의 수에 영향을 끼치므로 copymap을 통해 복제하여 사용한다.
-
처음 que에 궁수의 위치를 넣고 bfs를 돌며, 적을 사살하면 bfs를 종료한다. 이렇게 총 3번 반복한다. bfs탐색시 궁수의 사거리 D를 벗어나는 칸은 탐색하지 않는다.
-
📢이문제에 핵심인 부분인데, 처음 궁수가 적을 쏘고, 두번째 궁수가 같은 적을 쏘면, 사살 수가 중복된다.
궁수는 동시에 쏘며, 중복하더라도 궁수의 공격턴이 끝나기 때문에 0으로 처리하면, 다른 적을 또 쏘게 된다.
따라서 궁수가 중복된 적을 쏘면,공격턴은 끝나되, 사살 수를 세지 않도록 해야한다.
if (copymap[nrow][ncol] == 1) {//처음쏘는 적이면 처치수 +1
enemy++;
copymap[nrow][ncol] = -1;
break outloop;
} else if (copymap[nrow][ncol] == -1) {//두번째 쏘는 적이면 처치수 계산 x
break outloop;
}-
이후 적을 전진시킨다. 이때 사살한적을 -1처리 했는데 0으로 바꿔준다.(나중에 적이 없는지 확인할때 0을 세기 위함)
-
맵을 다시 탐색하며 0인 수를 세서 맵전체가 0이 될때까지 3,4,5동작을 반복한다.
후기
솔직히 말하자면 내 코드 시간복잡도 측면에서 구리다.
-
다른 사람 풀이 보니까 적의 인덱스만 리스트에 담아서 그 안에서만 탐색하는 경우도 있었는데, 나는 그냥 매번 copymap 만들어서 맵 전체를 탐색한다.
-
그리고 맵 전체를 탐색하며 적을 전진시키고, 다시 맵 전체를 탐색하여 적이 있는지 확인한다.
-> 아마 적의 수를 처음 입력받을때 세고, 사살하면서 적의 수를 감소시켜서 0일때를 구하는 방법이 더 탐색시간이 적을 것이다.(할려다 실패함) -
또 인상깊은 풀이중에 적을 전진시킨다 생각말고 맵의 크기를 아래서부터 줄이는 풀이도 있었다.
나는 구현에 초점을 맞춰서 문제에서 준 그대로 순서대로 구현했다.
1. 궁수가 적을 쏜다.
2. 전진한다.
3. 적이 0인가?
당연히 효율적으로 푸는게 뛰어난 개발자라고 생각하지만, 나는 문제를 풀어내냐가 가장 중요하기 때문에, 앞으로도 가장 쉽게 떠올릴 수 있는 방법대로 풀 예정이다.
나중에 잘 해지면 시간복잡도도 생각해보고, 객체지향원리도 생각해보겠다.
(시험붙고나서)
