[BOJ] 삼성 sw 역량 테스트 A형 기출 :: 백준 17135번 캐슬 디펜스 (조합, 시뮬레이션)

BOJ 17135번 캐슬 디펜스 문제 자바(java) 풀이

• 랭크 : 골드4
• 삼성 SW 역량 테스트 A형 기출문제
• 백준 17135번 캐슬 디펜스
  
  
  

문제정리

1. 게임 맵은 NxM 크기이다. 1x1 크기의 칸으로 이루어져 있다.
2. 각 칸에 포함된 적의 수는 최대 하나이다.
3. 격자판 N+1번 행의 모든 칸에는 성이 있다.
4. 궁수 3명을 배치하려고 함
   4.1 궁수는 성이 있는 칸에 배치 가능. 하나의 칸에는 최대 1명의 궁수만 있을 수 있음
   4.2 턴 마다 궁수는 적 하나 공격 가능. 모든 궁수는 동시에 공격
   4.3 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적. 그러한 적이 여럿이면 가장 왼쪽에 있는 적 공격
   4.4 공격받은 적은 게임에서 제외
5. 궁수의 공격이 끝나면 적이 이동한다.
   적은 아래로 한칸 이동. 성이 있는 칸으로 이동한 경우 게임에서 제외
6. 모든 적이 격자판에서 제외되면 게임 over

• 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수 계산

• 격자판 상태
  0: 빈칸
  1: 적
  
  
  

문제풀이

이 문제는 모든 문제가 그렇지만 문제를 잘 읽고 시작해야 합니다.
중요한 점은 적과의 거리가 우선이고 같은 거리에 있는 적이 여러명 있다면 그중 가장 왼쪽에 있는 적을 처치합니다.
가장 왼쪽의 적을 골라내기 위해서 sorting을 진행하면 됩니다.

1. width의 크기 중에 3 곳을 뽑는 모든 경우를 따져주어야 한다.
   크기가 4라면 (012), (013), (023), (123) 총 4가지가 가능하다. (₄C₃)
2. 배치를 하고 거리 D 안에 드는 적 들중 가장 왼쪽의 적(열의 index가 가장 작은 곳에 있는 적)들을 찾는다.
   거리가 우선이고 왼쪽 부터 찾으면 됩니다. 거리 1일때 부터 적을 찾아나갑니다.
   거리가 1일때 찾지 못했다면 거리2,3.. D까지 찾아갑니다.
   거리가 1인 곳은 1곳, 2인 곳은 3곳, 3인 곳은 5곳, N인 곳은 2N-1 구역이 있습니다. 이를 이용해 최적화합니다.
   거리가 2인 곳에서 적을 찾았다면 거리가 2인 곳에 있는 적 모두를 찾습니다.(위치 저장)
   그래서 적들의 위치를 행위치 기준 정렬하여 맨 왼쪽에 있는 적을 찾아 제거하면 됩니다.
3. 적의 위치를 아래로 한 칸 내린다.
4. 모든 적이 N=1로 사라질때까지 반복한다. 이를 배치 가능한 모든 경우에 대하여 반복한다.

• map의 초기 상태를 기억하기 위해 복사해서 사용한다.
• 자세한 내용은 주석에 달아두었으니 참고하시기 바랍니다!
• 문제를 거의 다 풀어서 생각이 낫는데 bfs로 탐색하는 것도 가능할 것 같습니다 (왼쪽, 위, 오른쪽 탐색)

캐슬 디펜스 자바(java) 코드

반례

• 반례1

  10 10 8
  1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  ans: 30

• 반례2

  5 5 2
  1 0 1 1 1
  0 1 1 1 1
  1 0 1 0 1
  1 1 0 1 0
  1 0 1 0 1
  ans 14

• 반례3

  5 5 3
  1 1 1 0 1
  0 1 1 0 0
  1 1 1 0 0
  0 1 1 0 0
  1 1 1 0 0
  ans 13

• 반례4

  10 10 1
  1 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 1
  ans 2

• 반례5

  15 15 10
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  ans 0