[C++] 백준 17135번 캐슬 디펜스

구현 / 시뮬레이션 문제.

삼성 A형 기출 문제에 수록되어 있는 문제다.

조합, 구현으로 문제를 풀었는데 그래프 탐색 이론으로도 풀 수 있다고 한다.

(그래프 탐색 이론은 상상도 못했고 지금도 잘 감이 안온다. 아마 궁수마다 BFS돌면서 제일 가까운 적을 죽이는 방식인 것 같다.)

골드 구현 문제를 많이 풀어봤다면 시도해볼법한 문제였다.

처음에 테스트 케이스를 다 맞춰서 문제를 푼 줄 알았는데, 자꾸 31%를 못넘었었다.

나는 적들의 좌표를 기록해주고, 거리와 c값에 따라 정렬해 준 후에 푸는 방식으로 풀었는데,

죽은 적들의 좌표를 기록에서 지워주지 않아서 틀리고 있었다.

 

문제풀이

각 문제의 조건들을 어떻게 해결할 수 있을까?

1. 두 위치의 거리는 |r1 - r2| + |c1 - c2|로 해결할 수 있다.

-><Math.h> STL에서 abs()메서드로 절대값을 사용한다.

2. 격자는 최대 15 x 15이며, 궁수는 높이 + 1, 즉 격자를 벗어나 제일 아래에 존재하게 된다.

-> 격자 배열을 [17][16]으로 선언해서 높이는 1 ~ 16으로 사용할 수 있게 생성한다.

3. 궁수는 최대 3명을 배치할 수 있다. 궁수가 배치된 후에는 적이 모두 사라질 때까지 다음 동작들이 반복된다.

1. 궁수마다 거리 D 이하, 가장 가까운 적을 공격한다. 이 때, 가장 왼쪽에 있는 적을 공격하는데, 같은 궁수가 같은 적을 공격할 수도 있다.
2. 공격 받은 적은 게임에서 제외된다.
3. 궁수들의 공격이 끝나면 적들이 아래로 한 칸 이동한다.
4. 이동한 적들 중, 궁수들과 같은 위치, 즉 (높이 + 1)의 위치로 온 적들은 게임에서 제외된다.
5. 모든 적이 제외되면 게임이 종료된다.

위와 같은 조건들에서, 궁수를 어떻게 배치해야 최대로 적들을 잡을 수 있는지를 물어보는 문제였다.

크게 보자면

1. 궁수 3명 배치 2. 적이 모두 격자에서 사라질 때까지 위 1~5진행

을 구현해야 한다.

 

크게 설명할 부분은 없는데, 구현하기는 또 까다로운 문제였다.

코드를 살펴보자.

사용한 변수와 STL

• EnemyForArcher 클래스 : 궁수가 적들을 공격할 때, 적들의 거리와 좌표를 기록해두기 위한 클래스이다.
• height, width, maxAttackDistance : 문제에서 입력받는 N, M, D이다.
• archerVec 벡터 : 궁수의 좌표를 기록하는 벡터이다. archerVec[0]이 첫번째 궁수, [1]이 두번째, [2]가 세번째 궁수의 좌표를 담고있다.
• enemyPointVec 벡터 : 게임을 시작하기 전, 최초 적들의 좌표이다.
• board 배열, boardForGame 배열 : board배열은 게임을 시작하기 전 최초의 격자칸, boardForGame 배열은 게임에서 쓰기위해 계속해서 상태를 바꿀 수 있는 격자칸이다.
• enemyInfoVec 벡터 : 궁수가 EnemyForArcher 클래스를 이용해서 적들과의 거리, 적들의 좌표를 담아두는 벡터이다.
• ans : 출력하는 결과값

<math.h> STL은 절대값 abs() 메서드 사용, <algorithm> STL은 정렬 메서드 sort()사용을 위해 만들었다.

구현한 정렬 메서드

거리가 더 작은 것과, 왼쪽(c가 더 작은)에 있는 것에 따라서 정렬이 되도록 comp 메서드를 만들었다.

 

메인함수

처음에 입력받는 N, M, D를 입력받은 후에, 격자 칸의 정보들을 입력받는다.

만일 격자의 정보가 1이라면 적이 있다는 뜻이므로 해당 좌표를 적의 좌표를 저장해두는 enemyPointVec에

넣어둔다.

 

입력이 끝났으면, setArcher()메서드를 통해서 궁수를 3명 뽑는다.

궁수 3명을 뽑는 메서드

매개변수 startArcherPoint는 궁수의 좌표중 c를 뜻한다.

어차피 궁수의 좌표는 (N + 1, 임의의 c)이다.

메인함수에서 1부터 시작했는데, 지금 아무 궁수도 뽑혀있지 않은 상태이므로,

archerIdx가 1이되고, 1부터 M까지 하나씩 궁수를 넣어보게 된다.

이런식으로 하면, 1을 선택하면 다음번째 궁수는 2라고 하면, 그 다음번째는 3, 4, 5, ...가 되므로,

중복으로 고려하지 않게 된다.

 

만일 archerVec의 크기가 3 이상, 즉 궁수가 3명 뽑혔다면 startGame()메서드로 게임을 진행한다.

게임 메서드 - 1

현재 궁수에서 적의 좌표들을 기록해두는 메서드

startGame() 메서드를 시작하면,

적의 수를 적의 좌표를 담는 벡터의 사이즈, 죽인 수를 0으로 초기화한다.

그리고 반복문을 통해서 boardForGame 배열을 board 배열로 초기화해서,

격자판을 게임을 진행시키기 전으로 초기화한다.

 

그러고 난 후에, 각 궁수의 index에 맞게 enemyInfoVec 벡터에 적들의 정보와 i번째 궁수와의 거리를 담아놓는다.

archerC는 i번째 궁수의 C 좌표이다. 궁수의 r좌표는 어차피 맨 아래보다 1칸 아래이므로, N + 1이 된다.

이 때, archerVec은 index가 0부터이고 나머지는 1부터 시작하므로 주의해야 한다.

 

saveEnemyInfo() 메서드를 통해, 적들의 정보와 궁수의 좌표를 통해서 enemyInfoVec 벡터에 적들의 정보를 넣고

sort() 메서드를 호출한다. 이 때, 비교 메서드로 위에서 구현한 comp() 메서드를 호출한다.

 

게임 메서드 - 2

그리고 첫번째로, 궁수가 공격을 시작한다.

이미 거리, 적의 C좌표대로 정렬이 되어있는 상태이므로, 0번째 좌표의 거리가 궁수가 공격할 수 있는 최대 거리보다

크다면 해당 궁수는 아무 적도 공격할 수 없는 상태이므로 break한다.

0번째 적이 공격할 수 있는 거리 내에 존재하고, 현재 상태가 1. 즉 다른 궁수에 의해 죽은 상태가 아니라면,

죽인 수 killCnt를 1증가시키고, 적의 수 enemyCnt를 1감소시키고, 해당 칸의 상태를 0으로 만든다.

그리고 curState가 1이 아니여도, 궁수는 해당 적을 다른 궁수와 동시에 공격할 수 있기 때문에

0번째 좌표를 만났다면 break를 한다.

priority_queue를 썼으면 좀 더 쉽게 풀 수 있었을 것 같기도 한데, 적들을 한 칸 아래로 이동시켜야 했으므로

복잡했을 것 같다.

 

게임 메서드 - 2

게임용 격자에서 먼저 적들을 한 칸 아래로 이동시킨다.

만일 높이가 N인데, 적을 아래로 이동시킨다면, 적이 게임에서 제외되므로 적의 수를 1 감소시킨다.

그 외에 경우에는 모두 위에서 아래로 이동시키는 작업을 하면 된다.

이 때, 범위를 0까지로 해야하는데, 0까지로 하지 않으면 1의 높이가 계속 유지되기 때문이다.

게임 메서드 - 3

그리고 적들의 정보를 저장해두는 벡터에서도 좌표를 업데이트 시켜줘야 한다.

만일, 이동시켰을 때, 격자 최대 높이보다 크거나(성에 도달했거나),  적이 죽은 상태라면

해당 인덱스의 적의 정보를 지우는데, 이 때 벡터 사이즈가 줄어들었으므로, j를 1 빼줘서 해당 index를

다시 탐색하게 만들어준다.

 

두 경우가 아니라면, 해당 좌표의 r에 +1을 해주고 거리를 새로 계산해준다.

그리고나서 바뀐 적의 정보를 토대로 sort()를 다시 호출해준다.

 

적이 격자에서 모두 사라져서 반복문을 탈출했다면, killCnt와 ans를 토대로 ans를 갱신해준다.

적의 좌표를 저장할 때, 죽은 적들을 제거해주지 않아서 계속 틀렸던 문제.

따로 반례는 안찾아봤는데 반례를 찾다가 그냥 이게 문제일까 싶어서 고쳐서 냈더니 맞았다.

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인이 가능하다.