APCS Sep 2021 - g276 Q2 [Python]

문제 설명:

n × m 보드에 k명의 마왕이 있습니다. i번째 마왕은 (r_i, c_i)에서 시작해 매 턴 (s_i, t_i)만큼 이동합니다. 즉, (x, y)에서 (x + s_i, y + t_i)로 이동합니다. 각 마왕은 고유한 r_i, c_i, s_i, t_i 값을 가집니다. 매 턴 이동하기 전에 현재 위치에 폭탄을 놓습니다. 폭탄이 있는 곳으로 이동하면 폭발하여 마왕과 폭탄이 사라집니다. 두 마왕이 동시에 같은 폭탄을 밟으면 둘 다 폭발하며, 같은 위치에 폭탄이 여러 개 있으면 함께 폭발합니다. 보드 밖으로 이동한 마왕도 사라집니다. 모든 마왕이 사라진 뒤 폭탄이 남아 있는 칸은 몇 개일까요?

n, m, k = map(int, input().split())

the_list = [[0 for _ in range(m)] for _ in range(n)]

boss = []

for _ in range(k):
    r, c, s, t = map(int, input().split())
    boss.append([r, c, s, t])

while boss:
    boom = set()
    to_remove = []

    for i in range(len(boss)):
        r, c = boss[i][0], boss[i][1]
        if the_list[r][c] == 0:  # 只有位置為0才要增加
            the_list[r][c] = 1

    for i in range(len(boss) - 1, -1, -1):  # range(起始值, 結束值(不會碰到), 增量) 
        r, c, s, t = boss[i]
        new_r, new_c = r + s, c + t
        
        if new_r >= n or new_c >= m or new_r < 0 or new_c < 0:  # 確認是否超出邊界
            to_remove.append(i)
            continue

        if the_list[new_r][new_c] > 0:
            if (new_r, new_c) not in boom:
                boom.add((new_r, new_c))
            to_remove.append(i)
        else:
            boss[i][0], boss[i][1] = new_r, new_c

    for i in sorted(to_remove, reverse=True): # 確保不會影響要移除的boss順序
        boss.pop(i)
    
    for (r, c) in boom:
        the_list[r][c] = 0

# 計算剩餘的炸彈數量
total = 0
for row in the_list:
    total += sum(row)

print(total)

---

풀이 보고서:

1. 입력: n, m, k와 각 마왕의 시작 위치 및 이동 벡터를 읽습니다.
2. 보드 초기화: 폭탄이 없음을 뜻하는 0으로 채운 n x m 배열 the_list를 만듭니다.
3. 매 턴 시뮬레이션: 모든 마왕이 현재 위치에 폭탄을 놓고 동시에 이동합니다. 보드 밖으로 나간 마왕은 제거합니다. 폭탄이 있는 칸에 도착하면 해당 칸을 0으로 만들고 마왕을 제거합니다.
4. 남은 폭탄 계산: 모든 마왕이 사라지면 the_list를 순회하며 남은 폭탄 수를 합산합니다.

주요 포인트

1. 인덱스로 삭제할 때는 역순으로 순회하기:

   • 앞에서부터 원소를 삭제하면 리스트 길이가 바뀌고 뒤쪽 인덱스가 이동합니다. 예를 들어:

     lst = [1, 2, 3, 4, 5]
     for i in range(len(lst)):
         if lst[i] % 2 == 0:
             lst.pop(i)
     

   lst[1]을 삭제하면 [1, 3, 4, 5]가 되지만 인덱스는 계속 증가하므로 다음 짝수인 4를 건너뛰게 됩니다.

   • 역순으로 순회하면 아직 방문하지 않은 원소의 인덱스가 바뀌지 않습니다.

     lst = [1, 2, 3, 4, 5]
     for i in range(len(lst) - 1, -1, -1):
         if lst[i] % 2 == 0:
             lst.pop(i)
     

   삭제한 위치 뒤의 원소는 이미 방문했으므로 영향을 받지 않습니다.

핵심 개념:

• 시뮬레이션
• 리스트 연산
• 집합

---

• [✔️] 필요하면 코드를 그대로 사용해도 됩니다.
• [✔️] 공유할 때 출처를 표시해 주세요.
• [✔️] 음… 이번에는 조금 느리네요.

이 글은 번체 중국어 원문을 AI로 번역했습니다. 의미나 표현에 차이가 있을 수 있으니 정확한 내용은 번체 중국어 원문을 기준으로 확인해 주세요.