강승현입니다
article thumbnail
반응형

문제로이동

 

17135번: 캐슬 디펜스

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

www.acmicpc.net


목차



    문제 설명

    • 비슷한 레벨의 BFS문제보다 어려웠다고 생각합니다.
    • 성벽은 가장 아래 행(안보이는 곳)에 존재합니다.
    • 해당 성벽에는 아처가 3명 있습니다.
      • 이 아처의 가능한 모든 위치를 고려하셔야 합니다.(3중 for문으로 해결)
    • 적군은 1턴(아처가 공격하고난 후) 후에 성벽으로 1칸 전진합니다.
      • 성벽에 닿게 되면 그냥 사라집니다.
    • 아처는 동일한 거리에 위치한 적군이 여러명일 경우, 가장 왼쪽에 있는 적군을 우선으로 죽입니다.
      • 이 경우에 한 적군이 아처 여러명에게 공격받을 수 있습니다.
    • 이 때, 아처가 공격하여 죽인 적군의 최대 수를 출력합니다.

    소스 코드

    jinhot님의 소스코드를 참고하였습니다.※

    소스코드에 주석은 가독성을 위해 대부분 지웠으며, Github 링크를 따라 가시면 각 줄에 주석(설명)을 달아놨습니다!

     

    풀이

     

    CODe1995/Baekjoon-Online-Judge

    백준 온라인 저지 문제풀이. Contribute to CODe1995/Baekjoon-Online-Judge development by creating an account on GitHub.

    github.com

    Python3

    ##########################################################
    import sys
    from collections import deque
    direction = [[0,1],[-1,0],[1,0],[0,-1]] #for BFS
    input = sys.stdin.readline
    def ip():return input().rstrip()
    def lip():return list(ip())
    def ips():return ip().split()
    def ii():return int(input())
    def mii():return map(int,ips())
    def lmii():return list(mii())
    ##########################################################
    height,width,D = mii()
    field=[ lmii() for _ in range(height)]
    
    def shoot(h_line,pos,s_field):
        for d in range(1,D+1):
            for left in range(d,-1,-1):
                diff = d-left
                hdiff = h_line - diff
                wdiff = pos - left   
                if diff>0 and 0<=hdiff<height and 0<=wdiff<width and s_field[hdiff][wdiff]==1:
                    return (wdiff,hdiff)
            for right in range(1,d+1):
                diff = d-right
                hdiff = h_line-diff
                wdiff = pos + right
                if diff>0 and 0<=hdiff<height and 0<=wdiff<width and s_field[hdiff][wdiff]==1:
                    return (wdiff,hdiff)            
        return None
        
    def simulation(pos):
        c_field = [line[:] for line in field]
        killed_cnt = 0
        for n in range(height,-1,-1):
            killed_list = []
            for p in pos:
                killed_enemy = shoot(n,p,c_field)
                if killed_enemy is not None:
                    killed_list.append(killed_enemy)        
            for killed_enemy in killed_list:
                if c_field[killed_enemy[1]][killed_enemy[0]]==1:
                    c_field[killed_enemy[1]][killed_enemy[0]]=0
                    killed_cnt+=1
        return killed_cnt
    
    max_kill = 0
    for i in range(width):
        for j in range(i+1,width):        
            for k in range(j+1,width):
                max_kill = max(max_kill,simulation([i,j,k]))
    print(max_kill)

    Java8

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.Arrays;
    
    public class Main {
    	static int H,W,D;//세로, 가로, 사거리
    	static int field[][];//필드 저장
    	static int max_kill = 0;//최대 킬 수가 저장되는 변수
    	public static void main(String[] args) throws IOException{
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
    		String input[] = br.readLine().split(" ");
    		H = Integer.parseInt(input[0]);
    		W = Integer.parseInt(input[1]);
    		D = Integer.parseInt(input[2]);
    		
    		field = new int[H][W];
    		for(int i  = 0 ; i<H;i++) {
    			input = br.readLine().split(" ");
    			for(int j = 0 ;j<W;j++)
    				field[i][j] = Integer.parseInt(input[j]);
    		}
    		
    		for(int i = 0 ; i<W;i++)
    			for(int j = i+1;j<W;j++)
    				for(int k = j+1;k<W;k++)
    					max_kill = Math.max(max_kill, simulation(i,j,k));
    		System.out.println(max_kill);
    	}
    	
    	public static int simulation(int a1,int a2,int a3) {
    		int c_field[][] = new int[H][W];
    		for(int i = 0 ; i < field.length;i++)	//2차원 배열 Deep Copy 수행
    			System.arraycopy(field[i], 0, c_field[i], 0, field[i].length);
    		int killed_cnt = 0;
    		for(int h=H; h>-1;h--) {
    			ArrayList<int[]> killed_list = new ArrayList<int[]>();
    			for(int p : Arrays.asList(a1,a2,a3)) {
    				int[] tmp = shoot(h, p, c_field);
    				if(tmp!=null) {
    					killed_list.add(tmp);
    				}
    			}
    			for(int[] killed_enemy:killed_list) {
    				if(c_field[killed_enemy[1]][killed_enemy[0]]==1) {
    					c_field[killed_enemy[1]][killed_enemy[0]]=0;
    					killed_cnt++;
    				}
    			}
    		}
    		return killed_cnt;
    	}
    	public static int[] shoot(int h,int p, int[][] c_field){
    		for(int d=1;d<D+1;d++) {
    			for(int left=d; left>-1; left--) {
    				int diff = d-left;
    				int hdiff = h - diff;
    				int wdiff = p - left;
    				if(diff>0 && 0<=hdiff && hdiff<H && 0<=wdiff && wdiff<W && c_field[hdiff][wdiff]==1) {
    					int[] ret = {wdiff, hdiff};
    					return ret;
    				}				
    			}
    			for(int right=1; right<d+1; right++) {
    				int diff = d-right;
    				int hdiff = h +-diff;
    				int wdiff = p + right;
    				if(diff>0 && 0<=hdiff && hdiff<H && 0<=wdiff && wdiff<W && c_field[hdiff][wdiff]==1) {
    					int[] ret = {wdiff, hdiff};
    					return ret;
    				}			 
    			}
    		}
    		return null;
    	}
    }

     

    반응형
    profile

    강승현입니다

    @CODe_

    포스팅에 대한 피드백을 환영합니다!
    피드백 작성자를 존중하며, 함께 공유하고 성장할 수 있는 기회가 되기를 기대합니다.의견이나 조언이 있다면 언제든지 자유롭게 남겨주세요!

    article prev thumbnail
    article next thumbnail
    profile on loading

    Loading...