1840번 - 스도쿠

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB653483722.289%

문제

스도쿠는 18세기 스위스 수학자가 만든 ‘라틴 사각형’이란 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이루어진다. 왼쪽 위 칸은 (1, 1), 오른쪽 아래 칸은 (9, 9)로 생각한다.

이 판에 수를 채우는 규칙은 다음과 같다.

  1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
  2. 굵은 선으로 구분되어 있는 3×3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

예를 들어 아래와 같은 경우, 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 빈칸에는 1이 들어가야 한다.

또한 다음과 같은 3×3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여 있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 81개의 칸을 차례로 채워 나가면 조건을 만족시키도록 퍼즐을 풀 수 있다. 하지만 숫자를 채워 나가는 도중에 실수가 있었다면 퍼즐을 완성하지 못하게 될 수도 있다. 예를 들어 29개의 칸을 채운 후 스도쿠 판이 다음과 같았다고 하자.

만일 30번째로 수 5를 (4, 6) 칸에 넣는다면, 현재 단계에서는 규칙에 위배되지 않지만 나머지 51개의 수를 어떻게 채워 넣는다고 해도 이 퍼즐은 풀 수 없는 퍼즐이 된다. 이처럼 가장 먼저 실수한 단계의 번호를 구하는 프로그램을 작성하시오.

입력

81개의 줄에 걸쳐 각 단계에서 숫자를 채울 칸의 좌표를 나타내는 두 정수와 그 칸에 적을 숫자가 빈 칸을 사이에 두고 순서대로 주어진다. 입력되는 모든 숫자는 1 이상 9 이하의 자연수이다.

출력

첫 줄에 가장 먼저 실수한 단계가 몇 번째인지 출력한다. 만일 실수한 곳이 없다면 -1을 출력한다.

예제 입력 1 

1 1 5
1 3 3
1 4 7
1 7 1
2 3 2
2 4 8
2 5 6
3 2 6
3 8 2
3 9 5
7 1 9
7 2 4
7 8 5
8 1 7
8 5 9
8 6 6
8 7 4
9 3 1
9 6 4
9 7 9
4 3 9
4 8 1
4 9 3
6 2 1
6 4 3
6 5 2
6 7 7
6 8 9
6 9 4
4 6 5
1 2 8
2 1 1
2 2 9
3 1 4
3 3 7
7 3 6
8 2 5
8 3 8
9 1 2
9 2 3
1 8 6
1 9 9
2 7 3
2 8 4
2 9 7
3 7 8
7 7 2
7 9 8
8 8 3
8 9 1
9 8 7
9 9 6
5 1 3
5 2 7
5 3 4
6 1 6
6 3 5
5 7 5
5 8 8
5 9 2
3 4 9
4 4 4
5 4 6
7 4 1
8 4 2
9 4 5
4 1 8
4 2 2
4 7 6
1 5 4
1 6 2
3 5 3
3 6 1
5 5 1
5 6 9
6 6 8
7 6 3
9 5 8
4 5 7
2 6 7
7 5 5

예제 출력 1 

30

예제 입력 2 

1 1 5
1 3 3
1 4 7
1 7 1
2 3 2
2 4 8
2 5 6
3 2 6
3 8 2
3 9 5
7 1 9
7 2 4
7 8 5
8 1 7
8 5 9
8 6 6
8 7 4
9 3 1
9 6 4
9 7 9
4 3 9
4 8 1
4 9 3
6 2 1
6 4 3
6 5 2
6 7 7
6 8 9
6 9 4
4 6 7
1 2 8
2 1 1
2 2 9
3 1 4
3 3 7
7 3 6
8 2 5
8 3 8
9 1 2
9 2 3
1 8 6
1 9 9
2 7 3
2 8 4
2 9 7
3 7 8
7 7 2
7 9 8
8 8 3
8 9 1
9 8 7
9 9 6
5 1 3
5 2 7
5 3 4
6 1 6
6 3 5
5 7 5
5 8 8
5 9 2
3 4 9
4 4 4
5 4 6
7 4 1
8 4 2
9 4 5
4 1 8
4 2 2
4 7 6
1 5 4
1 6 2
3 5 3
3 6 1
5 5 1
5 6 9
6 6 8
7 6 3
9 5 8
4 5 5
2 6 5
7 5 7

예제 출력 2 

-1

출처

  • 데이터를 추가한 사람: amel
  • 문제를 만든 사람: author5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)