arr = []
for _ in range(9):
arr.append(list(map(int, input().split())))
row = [{1, 2, 3, 4, 5, 6, 7, 8, 9} - set(arr[i]) for i in range(9)]
exis_col = []
for i in range(9):
exis_col.append(set([arr[j][i] for j in range(9)]))
col = [{1, 2, 3, 4, 5, 6, 7, 8, 9} - exis_col[i] for i in range(9)]
row_start = [0, 3, 6]
col_start = [0, 3, 6] # box를 위해
box = []
for i in range(3):
for j in range(3):
lst = set()
for x in range(row_start[i], row_start[i] + 3):
for y in range(col_start[j], col_start[j] + 3):
lst.add(arr[x][y])
box.append(lst)
for i in range(9):
box[i] = {1, 2, 3, 4, 5, 6, 7, 8, 9} - box[i]
blank = []
cnt = 0
for i in range(3):
for j in range(3):
for x in range(row_start[i], row_start[i] + 3):
for y in range(col_start[j], col_start[j] + 3):
if arr[x][y] == 0:
blank.append((x, y, 3 * i + j)) # 3* i + j 는 box number
cnt += 1
nums = [0] * cnt
def find(cur):
if cur == cnt:
for i in range(cnt):
pos = blank[i]
arr[pos[0]][pos[1]] = nums[i]
for i in range(9):
string = str(arr[i])[1 : -1]
string = string.replace(",","")
print(string)
exit()
pos = blank[cur]
candidate = row[pos[0]] & col[pos[1]] & box[pos[2]]
if candidate: # 공집합이 아니면
for x in candidate:
row[pos[0]].remove(x)
col[pos[1]].remove(x)
box[pos[2]].remove(x)
nums[cur] = x
find(cur + 1)
row[pos[0]].add(x)
col[pos[1]].add(x)
box[pos[2]].add(x)
find(0)box를 어떻게 처리해야할지 고민이어서
row_start = [0, 3, 6]
col_start = [0, 3, 6] # box를 위해
box = []
for i in range(3):
for j in range(3):
lst = set()
for x in range(row_start[i], row_start[i] + 3):
for y in range(col_start[j], col_start[j] + 3):
lst.add(arr[x][y])
box.append(lst)
for i in range(9):
box[i] = {1, 2, 3, 4, 5, 6, 7, 8, 9} - box[i]
blank = []
cnt = 0
for i in range(3):
for j in range(3):
for x in range(row_start[i], row_start[i] + 3):
for y in range(col_start[j], col_start[j] + 3):
if arr[x][y] == 0:
blank.append((x, y, 3 * i + j)) # 3* i + j 는 box number이런 식으로 처리했는데 이 부분이 바이트를 많이 먹은거 같다.
좀더 간단하게 할 방법은 없었을까?
우선 다른 사람의 코드를 읽어보자.
jinik9903님의 코드
1000ms가 걸린 649바이트짜리 간결한 코드이다.
import sys
def dfs(pointer, l):
if pointer == l:
for r in d: print(*r)
sys.exit() # 나랑 같은 생각인데 *r 이 무슨 의미인지 모르겠다
r, c = z[pointer] # pointer는 현재 몇번째 칸이냐를 가리키는 변수
avail = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for i in d[r]: avail[i] = 0 # d[r]에 있는 건 불가
for i in range(9): avail[d[i][c]] = 0 # c에 있는 것도 사용 불가
rr, cc = 3 * (r // 3), 3 * (c // 3)
for i in range(3):
for j in range(3): avail[d[rr + i][cc + j]] = 0
# 박스를 이렇게!
for i in [ind for ind, v in enumerate(avail) if v == 1]:
# 리스트 컴프리헨션은 이렇게!
d[r][c] = i # 미리 바꿔놓네
dfs(pointer+1, l)
d[r][c] = 0
d = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]
# d는 이차원 배열
z = [(r, c) for r, arr in enumerate(d) for c, v in enumerate(arr) if v == 0]
# enumerate 는 인덱스와 성분을 함께 리턴한다.
# 즉, r은 행, c는 열이 된다.
dfs(0, len(z)) # len(z)는 빈칸의 개수가 된다.나랑 아이디어는 비슷하나 set을 안 써서 이게 더 빠른 것 같다.
set을 굳이 만드는 과정이 나는 너무나 복잡했다....
결론 : 적은 수를 쓸 때는 set이 더 비효율적!
여기서는 avail배열과 rr, cc를 눈여겨보자.
(rr, cc는 Z를 풀었으면 충분히 저렇게 생각할 수 있는 것)
