1. 문제 조건
문제 조건이 정말 많고 다양해서 문제를 잘 읽어야하는 문제였다. 당장 코드부터 써가는 버릇을 고치려고, 설계부터 하고 코드를 다 짰지만 문제를 꼼꼼히 읽지 않아 엉망진창으로 설계한 코드를 짜버리고 말았다.
문제가 복잡할 수록 조건을 잘 정리해서 빠지는 부분이 없게 설계하도록 주의해야겠다.
본 문제는 배열 내에 있는 적을 맨 아래행에 궁수를 배치해 적을 잡는 게임을 코드로 설계하는 문제이다. 게임의 규칙은 아래와 같다.
1. 궁수를 성이 있는 칸인 배열의 맨 아래행(N+1번째 행)에 3명 배치한다.
2. 궁수는 각 턴마다 적 하나를 죽이며, 세 명의 궁수는 동시에 공격한다. 즉, 여러 궁수가 하나의 적을 동시에 공격할 수 있다.(적은 각 칸에 최대 한명만 존재할 수 있다.)
3. 궁수가 죽일 적이 결정되는 조건은 다음과 같다.
- 맨해튼 거리로 가장 가까운 적을 죽인다.
- 가장 가까운 거리에 있는 적이 여럿일 경우, 가장 왼쪽에 있는 적을 죽인다.
4. 궁수에게 공격받은 적은 게임에서 제외된다.
5. 궁수의 공격 턴이 끝나면 모든 적은 한 칸 아래로 이동한다.
6. 적이 성이 있는 칸(N+1번째 행)에 오면 게임에서 제외된다.
7. 모든 적이 게임에서 제외되면 게임이 종료된다.
2. 아이디어 및 구현
위 규칙을 어떻게 구현할지 설계해보자.
우선 아래와 같이 크게 세가지 파트로 나눌 수 있다.
1) 궁수를 배치한다.
2) 각 궁수가 죽일 적을 찾고, 동시에 죽인다.
3) 남은 적을 한칸씩 내린다.
각 파트별로 구현 아이디어를 내보자.
1) 궁수배치
3명의 궁수가 위치할 열 인덱스만 정하면 된다. (행은 n으로 고정이다.) 0 ~ m 중 3개의 조합을 구하는 함수를 만들어 재귀로 구현해보자.
현재까지 몇명을 뽑았는지와 직전에 어느 자리까지를 마지막으로 뽑았는지를 매개변수로 전달하여, 이번에 뽑는 궁수는 그 이후 인덱스부터 뒷 인덱스까지 for문으로 보며 for문의 각 i 자리에 궁수를 넣고, 다음 재귀를 호출하는 방식을 생각했다. 설명만으로는 잘 이해가 가지 않으니, 해당 부분을 직접 구현한 함수를 아래에서 살펴보자.
def set_archer(cnt, idx):
if cnt == 3:
# 현재까지 세팅한 궁수 자리에서 게임 진행하기
game()
return
#중복이 되면 안되므로 위와 직전에 idx-1까지 cnt-1번째 궁수 자리로 고안했다면,
#이번 cnt번째 궁수의 자리는 그 이후 자리부터 고려
#또한, 앞으로 뽑아야할 남은 궁수 수는 3-cnt이므로,
#앞으로 넣을 수 있는 자리의 수가 남은 궁수 수만큼이 될 때까지만 고려하도록 index를 m+1-(3-cnt)로 세팅
for i in range(idx, m-(3-cnt)+1):
archer[cnt] = i #궁수 뽑고
set_archer(cnt+1, i+1) #다음 궁수 뽑기 위해 호출
궁수 배치를 마쳤다면, 이 배치를 활용해 궁수로 적을 공격하고, 적이 내려오는 과정을 게임판에 적이 없어질 때까지 반복해야한다.
따라서 전체 게임판에 있는 모든 적을 Queue에 넣어두고 궁수마다 Queue의 적을 모두 확인하며 공격할 적을 찾고, 또 이 Queue를 활용해 모든 적을 한칸씩 내리는 방법을 활용했다. 아래에서 자세히 살펴보자.
2) 배치된 궁수를 활용해 적 죽이기
각 궁수별로 for문을 돌아 한명씩 어떤 적을 죽일 수 있는지 정하려고 했다. 이 때 주의할 점은, 모든 궁수는 동시에 적을 공격하고, 같은 적을 공격할 수 있으므로, 적이 보이자마자 공격하여 게임에서 배제시키면(Queue에서 적을 없애면), 다음에 공격할 적을 찾을 궁수가 공격하는 적이 달라질 수 있다. 따라서 우선 모든 궁수가 각각 어떤 적을 공격할 지 정하기만 하고, 공격할 적이 모두 결정되면 한번에 Queue에서 해당 적을 제외시켜야 한다.
또한, 궁수가 공격할 최단 거리의 적이 여럿일 경우 가장 왼쪽에 있는 적을 죽여야하기 때문에 Queue에 넣는 순서를 잘 고려하거나, 혹은 공격할 적을 갱신할 때 열 좌표를 비교하여 갱신해야한다.
3) 남은 적을 한칸씩 내리기
2)에서 공격받은 적은 게임에서 배제되므로, Queue에서 제거하는 방식으로 공격을 처리한다. 그런 후 Queue에 남은 값들은 아직 게임판에 배치된 적들이므로 Queue에서 꺼내서 한칸 아래로 이동 가능한지 확인하고, 게임판에서 배제되지 않는다면 한칸 내린 좌표를 다시 Queue에 넣는 방식으로 적의 위치를 변경했다.
2), 3)을 연달아 구현한 함수 코드를 주석과 함께 살펴보자.
def game():
global answer
# 처음 적의 위치를 deque에 넣기 (본 배열을 건드리지 않기 위함)
q = deque([])
#이 때, 최단 거리가 같은 적이 여럿이면 왼쪽 열이 우선이므로!!
# 반드시 for c in range(m)부터 해줘야 한다.
# 이 순서를 지키지 않을거라면, 공격할 적이 여럿일 경우
# 공격할 적을 갱신할 때, 열 번호를 잘 비교해서 갱신해야한다.
for c in range(m):
for r in range(n - 1, -1, -1):
if arr[r][c] == 1:
q.append((r, c))
#이번 게임에서 적을 공격한 횟수를 저장할 변수
kill = 0
#Queue에 원소가 있을 때 = 게임판에 적이 존재할 때
while q:
#적을 공격한 횟수가 중복되지 않도록(여러 궁수가 같은 적을 공격할 때)
#set으로 공격할 적을 관리할 것
kill_set = set()
#Queue 원소의 개수가 중간에 변동이 발생해도 적을 탐색할 때
#Queue에 존재했던 적들만 고려할 수 있도록
#그 당시 queue의 len 기억
now_enemy_cnt = len(q)
#각 궁수마다 어떤 적을 공격할지 기록
kill_lst = [(-1, -1) for _ in range(3)]
# 죽일 적 목록 만들기 (최단거리로!!)
for i in range(3):
#이번 궁수가 공격할 수 있는 적의 최단거리
min_d = n * m * 2
#이번 궁수
arc = archer[i]
#현존하는 모든 적 탐색
for j in range(now_enemy_cnt):
#현재 살펴볼 적
now = q.popleft()
#현재 살펴보는 적과의 거리
now_dist = distance(n, arc, now[0], now[1]) # 거리 계산
#주어진 조건에 부합하고 최단거리 갱신되면
if now_dist <= d and now_dist < min_d:
#이 적을 리스트에 기록
kill_lst[i] = now
#최단거리도 갱신
min_d = now_dist
#아직 공격 전이므로 다시 queue에 넣어주기(다음 궁수를 위해서!)
q.append(now)
#적을 죽이는게 가능하면(불가능할 수도 있으므로 체크해야 함)
if kill_lst[i] != (-1, -1):
#set에 넣기(궁수들이 같은 적을 죽이는 상황도 고려하기 위해)
kill_set.add(kill_lst[i])
#set에 있는 적들은 queue에서 제거(궁수들이 공격)
for e in kill_set:
q.remove(e)
kill += 1
now_enemy_cnt = len(q)#현재 queue 기록
# 적 한칸 내리기
for j in range(now_enemy_cnt):
now = q.popleft() #적을 queue에서 꺼내서
if now[0] + 1 >= n: #게임판에서 배제되는지 확인
continue#배제
q.append((now[0] + 1, now[1])) #배제 안되면 다시 queue에 1칸 아래 이동시킨 적 넣기
#while문 종료되면 모든 적이 게임판에서 배제된 것이므로
#kill값과 answer 비교 후 갱신
answer = max(kill, answer)
3. 시행착오
정말 많은 시행착오를 거쳤다.
1) 기존 배열에서 적을 아래로 이동시켰다.. 본 문제는 궁수가 배치되는 상황이 여러가지라, 첫번째로 궁수를 배치한 상황에서 입력된 배열 값을 수정하면 다음에 고려할 궁수배치에서는 적을 몇번이나 죽일 수 있는지 정확하게 파악할 수가 없다. 따라서 기존 배열을 건드는 것이 아닌, 다른 방법으로 적의 위치를 파악하여 공격하고, 적을 이동시켜야한다. 따라서 처음엔 배열 값을 수정했다가 무한루프가 도는 실수를 했고, 그 후엔 입력 배열은 절대 건드리지 않고, Queue에 모든 적을 넣어 관리함으로써 문제를 해결했다.
2) 궁수가 적을 동시에 공격한다는 사실을 고려하지 못했다.
1)에서 Queue로 적을 관리하는 방식으로 바꾼 후, Queue에서 꺼낸 적이 궁수가 공격할 적이면 다시 Queue에 넣지 않아 다음 궁수가 해당 적이 최단거리였음에도 공격하지 못하는 상황이 발생했다. 이럴 경우, 그 적이 아닌 엉뚱한 적을 공격해 정확한 공격횟수가 안오지 않게 됐다.
3) 최단 거리가 여럿이면 가장 왼쪽에 있는 적을 공격해야한다는 사실 망각
Queue에 넣을 적을 탐색하는 단계에서 행 for문부터 돌았더니, 행으로는 더 멀지만 열이 더 왼쪽인 적을 먼저 Queue에서 꺼내지 못했고, 최단거리 갱신할 때만 공격할 적을 정하는 방식을 정했기 때문에 엉뚱한 적을 공격하는 상황이 발생했다.
이 문제를 해결하기 위해 나는 for문의 순서를 바꿨다. 하지만, 공격할 적과 최단 거리를 갱신하는 부분에서 min_d와 비교할 때 등호를 추가하고, 공격할 적의 열 값을 비교하는 부분을 추가해도 해결가능하다.
이 외에도 ....
set에는 list를 넣을 수 없다는 사실을 배웠고(그래서 튜플을 활용했다.), 적 한칸 내릴 때 아래 적이 있고 없고 상관없이 모든 적이 일괄적으로 내려오므로 아래에 적이 있든 없든 그냥 내려야하는데 그러지 않았던 실수,, 등등
고생했습니다 나자신...
최종 코드 여깄습니다
from collections import deque
n, m, d = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
arr.append([0] * m)
answer = 0
archer = [0] * 3
def set_archer(cnt, idx):
if cnt == 3:
# 현재까지 세팅한 궁수 자리에서 게임 진행하기
game()
# print(archer)
return
for i in range(idx, m-(3-cnt)+1):
archer[cnt] = i
set_archer(cnt+1, i+1)
def distance(y, x, r, c):
return abs(y - r) + abs(x - c)
def game():
# print("======",archer,"========")
global answer
# 처음 적의 위치를 deque에 넣기 (본 배열을 건드리지 않기 위함)
q = deque([])
for c in range(m):
for r in range(n - 1, -1, -1):
if arr[r][c] == 1:
q.append((r, c))
kill = 0
while q:
# print('----------------')
kill_set = set()
now_enemy_cnt = len(q)
kill_lst = [(-1, -1) for _ in range(3)]
# 죽일 적 목록 만들기 (최단거리로!!)
for i in range(3):
min_d = n * m * 2
arc = archer[i]
for j in range(now_enemy_cnt):
now = q.popleft()
now_dist = distance(n, arc, now[0], now[1]) # 거리 계산
if now_dist <= d and now_dist < min_d:
kill_lst[i] = now
min_d = now_dist
q.append(now)
if kill_lst[i] != (-1, -1):
kill_set.add(kill_lst[i])
# print(kill_lst)
for e in kill_set:
q.remove(e)
kill += 1
now_enemy_cnt = len(q)
# 적 한칸 내리기
for j in range(now_enemy_cnt):
now = q.popleft()
if now[0] + 1 >= n:
continue
q.append((now[0] + 1, now[1]))
answer = max(kill, answer)
set_archer(0, 0)
print(answer)
'Learning-log > Algorithm 문풀' 카테고리의 다른 글
| 백준 20183번 골목 대장 호석 - 효율성 2 (Python) .. 우당탕탕 시행착오들.. (0) | 2024.08.18 |
|---|---|
| (Python) 백준 2164번 카드2 (0) | 2024.07.20 |
| 백준 12904번. A와B (Java) (0) | 2024.04.12 |
| 백준 1240번. 노드사이의 거리 (Java) (0) | 2024.02.16 |
| 백준 2579번 계단 오르기(Java) (0) | 2023.10.01 |
