Python으로 푸는 SW Expert Academy 1974. 스도쿠 검증

1974. 스도쿠 검증

문제는 스도쿠 조건에 따라

숫자가 잘 놓여져 있는지 확인할 수 있도록 검증하는 코드를 짜야한다.

삼성 SW Expert Academy에서 푼 문제 리스트 보러 가기

github에서 코드 보기

문제 조건

스토쿠는 숫자퍼즐로 가로 9칸 세로 9칸으로 이루어져 있는 2차원 배열에 1부터 9까지의 숫자를 채워넣는 퍼즐이다.

같은 줄에 1에서 9까지의 숫자를 한번씩만 넣고, 3*3 크기의 작은 격자 또한, 1에서 9까지의 숫자가 겹치지 않아야 한다.

문제 풀이

주어진 테스트 케이스를 모두 통과하려면, 3*3 형태로 나눈 구역에서도 스도쿠의 조건이 충족해야만 모든 테스트 케이스를 통과할 수 있다.

가로, 세로 체크하는건 너무 쉽고 3*3 구역을 체크하는게 이 문제의 핵심인데, 사실상 노가다로 9개의 for문을 돌려도 답은 나온다. 

시간 초과가 걸릴지 안걸리지는 모르겠다. 나는구역별 스도쿠 조건 체크는 for문을 한번 돌려서 문제를 풀었다.

총 81개의 원소를 순회한다, 스도쿠는 총 9개의 구역으로 나눌 수 있다. 그리고 원소의 순서가 27로 나눠질때마다 3개씩 구역을 묶어 상, 중, 하로 나눌 수 있다.

3의 배수가 나올때마다 3개의 구역에 번갈아 가면서 담는다. 코드를 보면 더 잘 이해가 간다.

→ 0	1	2	3	4	5	6	7	8
9	10	11	12	13	14	15	16	17
18	19	20	21	22	23	24	25	26
→ 27	28	29	30	31	32	33	34	35
36	37	38	39	40	41	42	43	44
45	46	47	48	49	50	51	52	53
→ 54	55	56	57	58	59	60	61	62
63	64	65	66	67	68	69	70	71
72	73	74	75	76	78	79	80	81

파이썬 코드

 
def solve(arr):
    for i in range(9):
        # 가로 검증
        if len(set(arr[i])) != 9:
            return 0
        # 세로 검
        temp = set()
        for j in range(9):
            temp.add(arr[j][i])
        if len(temp) != 9:
            return 0
 
    lineArray = [set(),set(),set()]
    index = 0
    # 9개의 구역 검사
    for r in range(0, 81):
        x = r // 9
        y = r % 9
        
        # 3개 구역씩 스도쿠 조건을 확인하고 비워준다
        if r != 0 and r % 27 == 0:
            if len(lineArray[0]) != 9 and len(lineArray[1])  != 9 and len(lineArray) != 9:
                return 0
 
        # 3개씩 나눠담기
        if r != 0 and r % 3 == 0:
            if index == 2:
                index = -1
            index += 1
 
        lineArray[index].add(arr[x][y])
    return 1
 
if __name__ == "__main__":
    tt = int(input())
    for t in range(tt):
        array = []
        for i in range(9):
            line = list(map(int, input().strip().split()))
            array.append(line)
        print("#{0} {1}".format(t+1, solve(array)))
 

#1974. 스도쿠 검증 #1974. 스도쿠 검증 python #python 1974 스도쿠 검증 #SW Expert Academy #sw expert 1974 #sw expert 1974 스도쿠 검증