시나위

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 요약 스도쿠 정답을 찾으면된다. 행과 열, 3X3 안에 1~9가 중복없이 들어가야한다. 접근 1. Brute-force 숫자를 넣어야하는 자리수는 최대 81개이고 1부터 9까지 모든 값을 넣어서 확인하려면 981 이 된다. O(232) 는 대충 42초 정도 걸리는데 이 값보다 크므로 이 방법으로 풀수 없다. 물론 0인 위치에서만 확인하면 되지만 찾아야하는 위치가 9개 이상이면 3초가 넘으므로 입력값을 알지 못하면 풀수 없다. 2. Backtracking 백..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 전형적인 백트래킹 문제이다. import sys; input = sys.stdin.readline def is_correct(value, r, c): global sudoku, find_list # 1 check row for i in range(9): if value == sudoku[r][i]: return False # 2 check col for i in range(9): if val..

https://acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net import sys input = sys.stdin.readline sudoku = [] zero_list = [] for i in range(9): tmp = list(map(int, input().split())) sudoku.append(tmp) for j in range(9): if tmp[j]: continue zero_list.append((i,j)) def backtrack(index): i..