백준 17135 캐슬디펜스 풀이 python, java

문제로이동

17135번: 캐슬 디펜스

---

목차

---

---

문제 설명

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

---

소스 코드

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

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

 

풀이

CODe1995/Baekjoon-Online-Judge

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;
	}
}