SWEA 1974번 스도쿠 검증

문제 바로가기

🙄 문제 이해

주어지는 2차원 배열이 스도쿠가 맞는지 검증하는 문제입니다.

스도쿠란 1~9 까지의 숫자(또는 n x n 에서 1~n까지)가 가로/세로/각 영역에 올바르게 분포되어 중복되지 않도록 채워나가는 게임입니다.

해당 문제는 채워진 스도쿠가 맞는지 검증, 다시 말해서 가로/세로/각 영역에 중복된 수가 있는지 체크하면 됩니다.

📝 문제 풀이

해쉬 테이블(딕셔너리)을 이용해 1~9를 True로 두고, 각 가로줄, 세로줄, 영역 에 대해서 맞는지 체크합니다.

영역 탐색의 경우 3x3의 영역이 3행 3열의 구조를 가지므로, 2중 루프 속에서 해당 영역을 탐색하는 또 다른 2중 루프로 구성했습니다.

가로/세로/영역의 순서로 진행하면서 하나라도 틀린게 있다면 스도쿠가 아니므로, 앞의 탐색이 참일 경우에만 다음 탐색을 수행하도록 합니다.

💻 Python 코드

#swea 스도쿠검증

#가로 | 세로 | 1/9칸 -> 1-9까지 전부 있는지 검증 -> hash

def garo(graph):
    for i in range(9):
        garo_n = {1:True, 2: True, 3:True, 4:True, 5:True, 6:True, 7:True, 8:True, 9:True}
        for j in range(9):
            if garo_n[graph[i][j]] == True:
                garo_n[graph[i][j]] = False
        if True in list(garo_n.values()):
            return False
    return True

def sero(graph):
    for i in range(9):
        sero_n = {1:True, 2: True, 3:True, 4:True, 5:True, 6:True, 7:True, 8:True, 9:True}
        for j in range(9):
            if sero_n[graph[j][i]] == True:
                sero_n[graph[j][i]] = False
        if True in list(sero_n.values()):
            return False
    return True

def cross(graph):
    
    for i in range(0,9,3):
        for j in range(0,9,3):
            cr_n = {1:True, 2: True, 3:True, 4:True, 5:True, 6:True, 7:True, 8:True, 9:True}
            for q in range(i,i+3):
                for w in range(j, j+3):
                    if cr_n[graph[q][w]] == True:
                        cr_n[graph[q][w]] = False
        if True in list(cr_n.values()):
            return False
    return True


T = int(input())
for t in range(1,T+1):
    graph = [list(map(int, input().split())) for _ in range(9)]
    answer = 0
    g,s,c = False, False, False
    #가로
    g = garo(graph)
    #세로 -> 가로가 참이면 수행
    if g:
        s = sero(graph)

    if g and s:
        c = cross(graph)

    if c:
        answer = 1
    
    print(f"#{t} {answer}")