[Softeer] 소프티어 나무공격 - Python

소프티어 나무공격

문제

환경 파괴범 때문에 화가 난 숲의 요정은 나무 공격을 진행하려 합니다.

나무 공격 진행시 투사체 5개가 생성되어 지정된 방향으로 전진합니다.

 

각 투사체와 최초로 접촉한 환경 파괴범은 사라지게 되며 이때 투사체 역시 동시에 사라지게 됩니다.

만약 투사체가 환경 파괴범과 마주치지 않는다면 조용히 사라지게 됩니다.

 

이는 n×m 크기의 격자에서 진행됩니다.

초기에 격자의 각 칸에는 숫자 0 또는 1이 적혀있으며 0은 비어있음을,

1은 환경 파괴범이 해당 위치에 서있음을 뜻합니다.

 

숲의 요정은 항상 격자의 왼쪽 방향에서 나무 공격을 진행하며, 총 2회 진행합니다. 

공격은 특정 행 L부터 행 R까지의 구간에 한하여 투사체를 만들어 진행하게 되며, 

모든 투사체는 행 변화 없이 정확히 오른쪽 방향으로만 진행하게 됩니다. 

 

투사체는 처음으로 만나는 환경 파괴범과 함께 사라지게 되며, 끝까지 만나지 않는 투사체는 조용히 사라지게 됩니다. 

L과 R의 차이는 항상 4이기 때문에 투사체는 항상 5개가 만들어짐에 유의합니다. 

 

 

문제 풀이

처음에 문제에서 주어진 이미지를 보았을 때, 그래프 탐색 문제인 줄 알았으나, 그렇지 않았다.그저 각 행에 몇 명의 파괴범이 있는지만 알 수 있다면, 매 공격마다 해당 행의 파괴범 수를 하나씩 줄이면 되는 문제이다.

 

따라서 각 행을 키 값으로, 몇 명이 존재하는지를 value로 갖는 해시를 하나 사용했다.이를 바탕으로 각 공격 마다, 해당하는 행의 파괴범의 수를 줄이고,마지막에선 전체 파괴범의 수를 더해서 출력했다.

정답코드

import sys

n, m = map(int, input().split())
graph = {}

for i in range(n):
    line = list(map(int, input().split()))
    graph[i+1] = sum(line)

for _ in range(2):
    start, end = map(int, input().split())

    for att in range(start, end+1):
        graph[att] = max(graph[att]-1, 0)

sum = 0
for _, val in graph.items():
    sum += val

print(sum)