[알고리즘 문제] 병아리 색칠하기 (Python / 파이썬)

문제

유니는 한달 용돈이 떨어져가는 미대생이다. 하지만 유니는 자신이 그린 병아리 그림에 노란색을 빨리 입히고 싶다.
유니의 병아리 그림은 0~N 구간으로 나눠져 있다고 볼 수 있다. 유니는 그 중 정해진 M개의 지점에 물감을 떨어뜨려 모든 구간이 색칠되게 하고 싶다.
각 위치에 떨어뜨린 물감의 양이 다르면 그림이 이상해질 수 있기 때문에 유니는 모든 위치에 같은 양의 물감을 떨어뜨리려고 한다. 또한 어떤 위치 p에 X만큼의 물감을 떨어뜨리면 
[p - X, p + X] 구간에 물감이 퍼지게 된다. 유니는 최소한의 물감을 사용해 그림을 모두 색칠하고자 한다. 각 위치에 물감을 최소 얼만큼 떨어뜨려야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트케이스의 수 T가 주어진다..
각 테스트케이스의 첫 줄에 N이 주어진다
각 테스트케이스의 두번째 줄에 M이 주어진다
각 테스트케이스의 셋째 줄에는 유니가 떨어뜨리려고 생각중인 좌표 M개가 주어진다. 모든 좌표는 0 이상 N 이하의 서로 다른 정수고, 오름차순으로 주어진다.
( 1 ≤ T ≤ 10, 1 ≤ N ≤ 100, 1 ≤ M ≤ N )

출력

각 테스트케이스마다 '#'과 테스트케이스의 번호, 공백을 출력한 뒤 유니가 떨어뜨려야 하는 물감의 양의 최소값을 출력한다.

---

문제 풀이

물감을 최소 얼만큼 떨어뜨려야 병아리를 모두 색칠할 수 있는지 구해야 합니다. 

완전 탐색을 이용해 물감의 양을 0부터 n까지 하나씩 M개의 지점에 떨어뜨려보고 

만약 모든 위치에 물감이 퍼지면 정답을 출력하도록 해주었습니다. 

 

0부터 n까지 False가 저장된 배열을 먼저 만들어줍니다. 

M개의 각 지점에 [p - x, p + x]까지 배열을 True로 만들어줍니다. 

그런 다음 배열을 0부터 n까지 모두 탐색하며 만약 False가 하나라도 있다면

모두 색칠되지 않은것이므로 False를 반환해주고 

그렇지 않다면 모두 색칠 된 것이므로 True를 반환해주었습니다. 

 

만약 True가 반환된다면 모두 색칠되었다는 것이므로 그때의 물감의 양을 출력해주면 됩니다. 

---

My Code

# 모두 색칠할 수 있는지 확인하는 함수
def check(x):
    color = [False] * (n + 1) # 모두 색칠되어 있지 않은 상태
    for i in range(m): # m개의 지점에
        for j in range(data[i] - x, data[i] + x + 1): # 물감을 색칠
            if j < 0 or j > n: continue # 범위를 벗어나면 넘어감
            color[j] = True # 색칠했다고 표시
    
    for i in range(n + 1): 
        if not color[i]: # 만약 색칠되지 않은게 하나라도 있으면
            return False # False 반환
    
    return True # 모두 색칠되었다면 True 반환 

for tc in range(int(input())):
    n = int(input()) # 구간의 끝
    m = int(input()) # 물감을 떨어뜨릴 좌표의 개수

    data = list(map(int,input().split())) # 물감을 떨어뜨릴 좌표

    for i in range(n + 1): # i만큼 물감을 떨어뜨림
        if check(i): # 모두 색칠 가능하면
            print('#' + str(tc + 1), end = ' ')
            print(i) # 물감의 양을 출력
            break    # 탐색 종료