메뉴 닫기

[BOJ] 17135 캐슬 디펜스 – 최적화까지

17135번: 캐슬 디펜스 (acmicpc.net)

이렇게 오랫동안 한 문제를 잡고 풀었던 적은 처음인것 같다. 예시로 주어진 테스트케이스는 다 맞췄는데 작동하지 않는 경우도 있었고, 디버깅 막판에는 예시로 주어진 테스트케이스에 이상하게 답이 나와서, 이부분에서 애를 많이 먹었다.

감격의 맞았습니다.

다행히 12시가 지나기 전에 풀어서 제출할 수 있었다.

풀다가 멘탈 나가는줄 알았다. 내가 얼마나 이때까지 그리디한 방식으로 테스트케스를 맞추는 코딩을 하고있었는지 또 한번 깨닫게 되었다. 테스트케이스에서 걸러지지 않는 경우가 있어서, 하나씩 디버깅하면서 코드를 봤더니, 예상했던대로 탐색조건이 잘못된 경우였다.

이번 문제는 조합 + 탐색 + 배열이 고루고루 섞인 아주 종합선물세트 같은 느낌이었다.
이번엔 다행히 배열의 복사에 대해서 저번에 공부한 덕분에 이 부분에서는 문제가 생기진 않았다.

접근방식은 정말 직관적으로 생각해서 풀었다. 처음엔 nextpermutation을 조합에 적용해서 while문안에서 시뮬레이션을 수행하려고 하다가, 이부분이 잘 안되어서 그냥 기존에 사용하던 재귀적 조합식안에 조합이 완성되면 시뮬레이션을 실행했다.

전체적인 흐름은 다음과 같다.

  1. N,M,D 입력받아 변수에 저장
  2. 입력받아서 문자열 배열에 적군의 위치 저장
  3. M열중 궁수 3명의 위치를 의미하는 pos배열을 조합으로 생성
  4. 생성된 조합마다 eliminate()메소드에서 죽인 적군의 수를 계산
  5. 적군의 수중 가장 큰 값을 eli 에 저장하고
  6. 출력

대충 이런식으로 된다. eliminate 가 핵심적인 파트인데, 우선 입력받은 행 단위로 작업을 수행한다.
궁수의 위치를 (N, 조합된 열 좌표 ) 로 설정하였고, 이를 기준으로해서 좌측, 상단, 우측으로 나누어서 탐색했다.
가까운 거리에있는 좌표부터 탐색하도록 for문에 D(사정거리)를 가지고 작성하였으며, 거리가 가까운순에서 먼 순으로 방문하기 때문에 처음 1(적군) 을 만나는 순간 for문을 탈출하고 이를 저장하여 queue에 넣어주었다.
예를 들어 distance 가 3이면 3명의 궁수가 각각 1일때를 기준으로 먼저 탐색을 수행하고 2, 3 증가하는 식으로 하였다.
그렇게 차근차근 가까운 좌표를 탐색하고나서 queue에서 꺼내면서 중복된 경우를 생각해서 죽은 적군을 다시 죽였다고 카운트하지 않도록 attack변수 값을 추가하는 동시에 map에서 값을 변경해 주었다.

queue에 등록된 모든 적군을 맵에서 제거하고 나면, 이제는 배열을 복사해서 내려오는 것과 동일하게 만들었다.
i-1 행의 배열을 i행으로 복사하였고, 0번째 행에는 Arrays.fill을 이용해 0으로 채워주었다. 배열을 복사하기위해서는 밑에서부터 거꾸로 올라가는 방식으로 복사해주어야 했다.

package _0217;

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

/*
 * 궁수는 항상 3명
 * 궁수의 위치  = map[N][?] N+1번째 행에 있음
 * 적을 맵에다가 위치시키기
 * 궁수의 위치를 조합을 이용해서 mC3 형태로 배치시키기
 * 각 배치마다 최대로 처리 가능한 적 계산
 * 최대 처리가능한 적의 최대값을 출력
 */
public class BOJ17135Castle {

	private static int N, M, D;
	static int[] pos =new int[3];//궁수의 위치
	private static char[][] map, map2;
	private static int eli;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		//N , M, D
		N = Integer.parseInt(st.nextToken()); //행의 수
		M =Integer.parseInt(st.nextToken()); //열의 수
		D =Integer.parseInt(st.nextToken()); //궁수의 공격제한 거리
		map = new char[N][M]; // N+1 번 행에는  모든 칸에 성
		map2 = new char[N][M]; // 복사한 배열
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0, k =0; j < M; j++, k+=2) {
				map[i][j] = line.charAt(k);
			}
		}
		eli = 0;
		combination(0,0 );
		System.out.print(eli);
	}
	//사정거리와 거리를 가지고 제거할 수 있는 적군의 수를 계산해서 리턴한다.
	private static void eliminate() {
		int attack = 0;
		Queue<int[]> list = new LinkedList<>();
		for (int k = 0; k < N; k++) { //행만큼 반복
			for (int i = 0; i < 3; i++) { //궁수마다 반복
				inner:for (int distance = 1; distance <= D; distance++) { //거리만큼 탐색해야함
				int posx= N; // 아쳐의 행
				int posy = pos[i]; //아쳐의 열
					//좌측 탐색
					for (int j2 = 1; j2 <= distance-1; j2++) { //거리 -1 번 반복
						if(posx-j2<0 || posy-distance+j2>=M ||posy-distance+j2<0 ) continue;
						if(map2[posx-j2][posy-distance+j2]=='1') {
							int[] temp = {posx-j2,posy-distance+j2};
							list.offer(temp);
							break inner;
						}
					}
					if(posx-distance < 0) continue;
					if(map2[posx-distance][posy]=='1') {
						int[] temp = {posx-distance, posy};
						list.offer(temp);
						break inner;
					}
					//우측탐색
					for (int j2 = 1; j2 <= distance-1; j2++) { //거리 -1 번 반복
						if(posx-(distance)+j2<0 || posx-(distance)+j2 >=N || posy+j2>=M ) continue;
						if(map2[posx-(distance)+j2][posy+j2]=='1') {
							int[] temp = {posx-(distance)+j2, posy+j2};
							list.offer(temp);
							break inner;
						}
					}
				}//거리 1부터 D까지 실행
			}//궁수마다 반복하는 for문
			//한줄 처리가 끝난 경우 큐에서 꺼내서 죽인사람++ 이미 죽은사람 -> map에서 0으로 변경
			while (!list.isEmpty()) {
				int[] is = list.poll();
				if(map2[is[0]][is[1]]!='0') {
					map2[is[0]][is[1]]='0';
					attack++;
				}
			}
			//배열 한칸아래로 이동
			for (int j = N-1; j >0;  j--) {
				System.arraycopy(map2[j-1], 0, map2[j], 0, M);
			}
			Arrays.fill(map2[0],'0');

		}//다음행
		eli = Math.max(attack, eli);
	}

	private static void combination(int cnt, int start) {
		if (cnt ==3) {
			for(int i = 0; i < N; i++) {
				System.arraycopy(map[i], 0, map2[i], 0, map2[i].length);
			}
			eliminate();
			return;
		}
		for (int i = start; i<M; i++) {
			pos[cnt]= i; 
			combination(cnt+1, i+1);
		}
	}
}

그러고보니 실행속도가 꽤 빨랐다. 음 여기서 더 최적화 할수도 있을것 같긴한데 나중에 시간남을때 한번 더 해봐야겠다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	private static int N, M, D;
	static int[] pos =new int[3];//궁수의 위치
	private static char[][] map, map2;
	private static int eli;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		//N , M, D
		N = Integer.parseInt(st.nextToken()); //행의 수
		M =Integer.parseInt(st.nextToken()); //열의 수
		D =Integer.parseInt(st.nextToken()); //궁수의 공격제한 거리
		map = new char[N][M]; // N+1 번 행에는  모든 칸에 성
		map2 = new char[N][M]; // 복사한 배열
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0, k =0; j < M; j++, k+=2) {
				map[i][j] = line.charAt(k);
			}
		}
		combination(0,0 );
		System.out.print(eli);
	}
	//사정거리와 거리를 가지고 제거할 수 있는 적군의 수를 계산해서 리턴한다.
	private static void eliminate() {
		int attack = 0;
		int[][] temp = {{-1,-1},{-1,-1},{-1,-1}};
		for (int k = 0; k < N; k++) { //행만큼 반복
			for (int i = 0; i < 3; i++) { //궁수마다 반복
				search:for (int distance = 1; distance <= D; distance++) { //거리만큼 탐색해야함
					int posy = pos[i]; //아쳐의 열
					//좌측 탐색
					for (int j2 = 1; j2 <= distance-1; j2++) { //거리 -1 번 반복
						if(N-j2<0 || posy-distance+j2>=M ||posy-distance+j2<0 ) continue;
						if(map2[N-j2][posy-distance+j2]=='1') {
							temp[i][0] = N-j2;
							temp[i][1]=posy-distance+j2;
							break search;
						}
					}
					if(N-distance < 0) continue;
					if(map2[N-distance][posy]=='1') {
						temp[i][0] = N-distance;
						temp[i][1]=posy;
						break search;
					}
					//우측탐색
					for (int j2 = 1; j2 <= distance-1; j2++) { //거리 -1 번 반복
						if(N-(distance)+j2<0 || N-(distance)+j2 >=N || posy+j2>=M ) continue;
						if(map2[N-(distance)+j2][posy+j2]=='1') {
							temp[i][0] = N-(distance)+j2;
							temp[i][1]= posy+j2;
							break search;
						}
					}
				}//거리 1부터 D까지 실행
			}//궁수마다 반복하는 for문
			for (int[] is : temp) {
				if(is[0]!=-1) {
					if(map2[is[0]][is[1]]!='0') {
						map2[is[0]][is[1]]='0';
						attack++;
					}
				}
			}
			for (int j = N-1; j >0;  j--) {
				System.arraycopy(map2[j-1], 0, map2[j], 0, M);
			}
			Arrays.fill(map2[0],'0');

		}//다음행
		eli = Math.max(attack, eli);
	}

	private static void combination(int cnt, int start) {
		if (cnt ==3) {
			for(int i = 0; i < N; i++) {
				System.arraycopy(map[i], 0, map2[i], 0, map2[i].length);
			}
			eliminate();
			return;
		}
		for (int i = start; i<M; i++) {
			pos[cnt]= i; 
			combination(cnt+1, i+1);
		}
	}
}

기존 queue를 이용하던 것에서 배열로 바꾸어주어서 메모리를 최적화해주었다. posx에서 반복되는 부분도 기존 N을 그대로 받아오기 때문에 posx 변수도 삭제했다.

감격스러운 7등!!메모리를 최대한 적게 사용하면서 시간도 나름 최적화 했다.

더 짧은 코드로 더 빠르게 푸신분은 어떤방식을 썻는지 궁금하다.

Related Posts

답글 남기기

이메일 주소는 공개되지 않습니다.

%d 블로거가 이것을 좋아합니다: