[알고리즘] 스토쿠 검사

(문제) 스토쿠 검사

---

스도쿠는 매우 간단한 숫자 퍼즐이다.

9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다.

예를 들어 다음을 보자.

위 그림은 스도쿠를 정확하게 푼 경우이다.

각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

완성된 9×9 크기의 수도쿠가 주어지면 정확하게 풀었으면 “YES”, 잘 못 풀었으면 ”NO”를 출력하는 프로그램을 작성하세요.

입력설명

첫 번째 줄에 완성된 9×9 스도쿠가 주어집니다.

출력설명

첫째 줄에 “YES” 또는 ”NO”를 출력하세요.

테스트케이스

입력예제	출력예제
1 4 3 6 2 8 5 7 9 5 7 2 1 3 9 4 6 8 9 8 6 7 5 4 2 3 1 3 9 1 5 4 2 7 8 6 4 6 8 9 1 7 3 5 2 7 2 5 8 6 3 9 1 4 2 3 7 4 8 1 6 9 5 6 1 9 2 7 5 8 4 3 8 5 4 3 9 6 1 2 7	YES
1 2 3 4 5 6 7 8 9 2 1 4 3 6 5 8 9 7 3 4 1 2 7 8 9 5 6 4 3 2 1 8 9 6 7 5 5 6 7 8 9 1 2 3 4 6 5 8 9 1 7 3 4 2 7 8 9 5 2 3 4 6 1 8 9 6 7 4 2 5 1 3 9 7 5 6 3 4 1 2 8	NO
1 4 3 6 2 8 5 7 9 5 7 2 1 3 9 4 6 8 9 8 6 7 5 4 2 3 1 3 9 1 5 4 2 7 8 6 4 6 8 9 1 7 3 5 2 7 2 5 8 6 3 9 1 4 2 3 7 4 8 1 6 9 5 6 1 9 2 7 3 8 4 5 8 5 4 3 9 6 1 2 7	NO
9 6 1 8 2 5 3 7 4 2 8 3 1 7 4 5 6 9 5 4 7 3 6 9 1 2 8 1 2 8 9 3 6 7 4 5 3 7 5 4 8 1 6 9 2 6 9 4 2 5 7 8 1 3 8 1 2 7 4 3 9 5 6 7 3 6 5 9 2 4 8 1 4 5 9 6 1 8 2 3 7	YES

---

해결방법

0~9 인덱스를 나타내는 리스트를 생성하거나 딕셔너리를 생성하여 반복문을 돌아서 각행 그리고 각열을 더해서 “최대값”이 반복하여 더한 번 수 보다 큰 것이 있는지 확인을 한다.

그리고 한 구역을 확인하는 방법은 4중 for 문을 돌려서 이용한다.

안쪽의 for 문 2개는 영역의 9개를 접근하는 것이고, 바깥의 for 문 2개는 다른 영역에 접근하기 위해서 사용한다.

---

코드

arr = [list(map(int, input().split())) for _ in range(9)]

flag = False

# 행, 열 확인
for i in range(9):
    ch = []
    for j in range(9):
        ch.append(arr[i][j])
        ch.append(arr[j][i])
    # 최대 숫자 1보다
    if max(Counter(ch).values()) > 2:
        flag = True
        print('NO')
        break

# 스도쿠 4중 for 문
if not flag:
    for i in range(3):
        for j in range(3):
            ch = []
            for k in range(3):
                for l in range(3):
                    ch.append(arr[i*3+k][j*3+l])
            if max(Counter(ch).values()) > 1:
                flag = True
                print('NO')
                break
        if flag:
            break
    else:
        print('YES')