[알고리즘 문제] 고장난 시계 (Python / 파이썬)

문제

유니는 예쁜 디지털 시계를 샀다.
그런데 아침에 일어난 유니는 깜짝 놀랐다. 시계의 특정 부분이 고장나서 불이 들어오지 않아 현재 시각을 알아볼 수 없었기 때문이다.
원래 정상적인 시계는 다음과 같은 형태로 0부터 9까지의 숫자를 표현한다.

여기서 '#'은 불이 들어오는 위치, '.'은 불이 들어오지 않는 위치다.유니의 고장난 시계는 불이 들어와야 하는 위치 중 일부에 불이 들어오지 않는다.
낙관적인 유니는 현재 시계 상태를 보고 몇 시 몇 분일지 가능한 경우를 모두 구한 뒤 그 중 가장 빠른 시각이 현재 시각이라고 생각하기로 했다.고장난 시계의 형태가 주어질 때, 유니가 생각하는 현재 시각이 몇 시 몇 분인지 출력하는 프로그램을 작성하시오

입력

첫째 줄에 테스트케이스의 수 T가 주어진다..
각 테스트케이스는 공백 한 줄로 시작한다.
그 후 다섯 줄에 걸쳐 시계의 상태가 주어진다.
( 1 ≤ T ≤ 10 )

출력

각 테스트케이스마다 '#'과 테스트케이스의 번호를 출력하고 한 줄 개행한 뒤 유니가 생각하는 현재 시각을 HH:MM 형태로 출력한다.

---

문제 풀이

입력으로 시계의 상태가 주어졌을 때 가능한 시각 중 제일 빠른 시각을 찾는 문제입니다. 

먼저 시계는 총 4개의 2차원 배열로 이루어져 있습니다. 

따라서 array[2차원 배열의 개수][2차원 배열의 세로][2차원 배열의 가로] 를 이용하여

시계의 상태를 입력 받을 수 있습니다. 

 

시계의 상태를 입력 받은 뒤 가능한 시:분 조합을 2중 for문을 이용해 모두 구해줍니다. 

입력 받은 시계의 상태가 각 시:분을 표현할 수 있는지 완전 탐색으로 탐색해줍니다.

 

array[0] 은 시의 첫번째 수를 나타내고 array[1] 은 시의 두번째 수를 나타내고

array[2] 는 분의 첫번째 수를 나타내고 array[3] 은 분의 두번째 수를 나타냅니다.

따라서 각 수를 나타낼 수 있는지 확인해주면 됩니다. 

만약, 원본의 '.' 가 있는 자리에 '#' 가 있다면 절대로 그 수를 만들 수 없다는 뜻입니다.

따라서 원본의 '.' 자리에 '#' 가 있다면 만들 수 없으므로 False를 반환해줍니다. 

이런 경우가 하나도 없다면 만들 수 있다는 뜻이므로 True를 반환해줍니다. 

 

만약 시:분 조합을 모두 나타낼 수 있다면 HH:MM 형태로 답을 출력해줍니다.

---

My Code

# 시계의 원본 
num = [ 
    ('###','#.#','#.#','#.#','###'),
    ('..#','..#','..#','..#','..#'),
    ('###','..#','###','#..','###'),
    ('###','..#','###','..#','###'),
    ('#.#','#.#','###','..#','..#'),
    ('###','#..','###','..#','###'),
    ('###','#..','###','#.#','###'),
    ('###','..#','..#','..#','..#'),
    ('###','#.#','###','#.#','###'),
    ('###','#.#','###','..#','###')
]

# x를 clock이 표현할 수 있는지 확인
def check2(clock, x):
    for i in range(5):
        for j in range(3):
            # 원본의 '.' 자리에 '#'가 절대 올 수 없음
            if clock[i][j] == '#' and num[x][i][j] == '.':
                return False  # 만들 수 없다는 뜻이므로 False 반환
    return True # 만들 수 있으면 True 반환

# 현재 시계의 상태가 시, 분의 각 수를 표현 할 수 있는지 확인
def check(h, m):
    if check2(array[0], h // 10) and check2(array[1], h % 10) and check2(array[2], m // 10) and check2(array[3], m % 10):
        return True # 표현 가능하다면 True 반환

for tc in range(int(input())):
    a = input() # 첫번째 줄은 공백 입력 

    array = [[0] * 5 for _ in range(4)] # 시계의 현재 상태를 저장
    for i in range(5):
        data = input().split()
        for j in range(4):
            array[j][i] = data[j]

    flag = False 
    for i in range(24): # 0~23시까지
        for j in range(60): # 0~59분까지
            if check(i, j): # 현재 시계가 표현 가능한 시간이면
                print('#' + str(tc + 1))
                if i < 10: print('0', end = '') 
                print(i, end = '') # 시 출력
                print(':', end = '')
                if j < 10: print('0', end = '')
                print(j)           # 분 출력
                flag = True # 최소 시간 찾았으므로 종료되도록 True
                break 
        if flag: # 최소 시간 찾았다는 것이므로 종료
            break