[백준] 17135 캐슬 디펜스

들어가기

• 17135. 캐슬 디펜스 문제는 삼성 코딩 테스트에 나오는 유형과 비슷한 문제입니다.
• 시뮬레이션 문제이기 때문에 예제를 활용하여 시뮬레이션을 돌려보고 나온 로직을 구현하는 것이 좋습니다.
• 또한 문제에서 제시하고 있는 조건들을 꼭 눈여겨봐야 합니다.

문제

• 게임은 N x M 격자판에서 진행됩니다. 
• N + 1 줄에는 캐슬이 있습니다. 이 캐슬을 지키기 위해서 3명의 궁수를 배치합니다.
• D는 궁수가 적을 공격할 수 있는 사정거리를 뜻합니다.
• 게임은 턴 제로 진행됩니다. 한 턴 마다 적이 한줄씩 아래로 내려옵니다.
• 캐슬까지 내려온 적은 격자판에서 사라집니다.
• 캐슬을 지키기 위해서 궁수들은 한 턴 마다 하나의 적을 공격할 수 있습니다.
• 궁수가 공격할 때 D(사정거리) 안에 있는 적만 공격 가능하며 그 중 가장 가까운 적을 공격합니다.
• 가장 가까운 적이 여럿 있을 때는 가장 왼쪽에 있는 적을 공격합니다.
  • 같은 거리에 있는 적 중에 가장 왼쪽을 공격합니다.
• 궁수들의 공격은 동시에 이루어 집니다. 그렇기 때문에 위 조건에 부합하면 같은 적이더라도 여러 궁수가 공격할 수 있습니다.
  
  • 궁수가 공격 후 적이 바로 제거되는 것이 아닙니다. 
  • 같은 적을 다른 궁수도 공격할 수 있기 때문에 턴을 종료한 다음 적을 제거해야합니다.
• 이와 같은 조건으로 제거할 수 있는 적의 최대수를 구하는 문제입니다.

풀이

• 위 조건을 가지고 예시를 보겠습니다. 공격 사정거리는 2(D)입니다.
• 첫번째 턴에서 궁수는 아래와 같이 적을 공격할 수 있습니다. (누적 최대 공격 적 : 3)

첫 번쨰 턴

• 두번째 턴에서는 궁수는 아래와 같이 적을 공격할 수 있습니다.
• 두번째 턴 종료후 누적 최대 공격할 수 있는 적은 총 5입니다.

두 번째 턴

 

• 엇 혹시 6아닐까 생각할 수 있습니다. 
• 두번째 턴에서 가운데 궁수가 노란색 선으로 표시한 적을 공격하면 최대 6명의 적을 공격할 수 있겠지만 그러나 주어진 조건에 어긋 납니다.
• 가운데 궁수의 입장에선 두 적의 위치는 동일하기 때문에 가장 왼쪽의 적을 공격해야 합니다.
• 그래서 6이 아니라 5입니다.

 

• 그러므로 같은 거리의 격자판을 방문 할 때는 순서가 중요합니다. 시계 방향으로 방문해야합니다.

• 적 공격한 것을 표시해놓고 각 턴이 종료되면 격자판에서 제거하는 것으로 구현하면 푸실 수 있을 것입니다.
• 아래는 참고한 예시들입니다.

입력
2 7 2
0 0 1 0 1 0 1
1 0 1 0 1 0 0
답 : 5

 

입력

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
답 : 14

입력
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
답 : 13

 

입력
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
답 : 30

소스 코드