시간초과 진짜 *같아서 진짜 아오
처음에 잘 모르겠어서 알고리즘 분류 본 거 인정
근데 진짜 풀이 안보고 잘 풀었는데 시간초과가 나서 아주 조금 찾아보니 0인 부분만 돌면 되겠구나 싶어서 그것만 보고 고쳤는데
시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과시간초과아아아아아ㅏ아아아ㅏ앍!!!!!!!!!!!!!!!!!!!
결국 pypy3으로 통과했다.
- pypy3 통과 코드
import sys
input = sys.stdin.readline
def check(i,j,p):
if p in board[i]:
return False
elif p in [board[k][j] for k in range(9)]:
return False
else:
x = (i//3) * 3
y = (j//3) * 3
for a in range(3):
for b in range(3):
if p == board[x+a][y+b]:
return False
return True
def backtracking(k):
if k >= len(zero):
for row in board:
print("".join([str(b) for b in row]))
exit()
i = zero[k][0]
j = zero[k][1]
for p in range(1,10):
if check(i,j,p):
board[i][j] = p
backtracking(k+1)
board[i][j] = 0
board = []
for _ in range(9):
row = input().strip()
board.append([int(r) for r in row])
zero = [(i,j) for i in range(9) for j in range(9) if board[i][j] == 0]
backtracking(0)- 파이썬 통과 코드
뭐가 그렇게 다른지 궁금해서 다른 사람 코드를 보고 고쳤다.
import sys
input = sys.stdin.readline
def possible_numbers(i,j):
return [l for l in range(1,10) if row_check[i][l] and col_check[j][l] and box_check[(i//3)*3+j//3][l]]
def backtracking(k):
if k >= len(zero):
for row in board:
print("".join(map(str, row)))
exit()
i = zero[k][0]
j = zero[k][1]
for p in possible_numbers(i,j):
board[i][j] = p # 스도쿠판 상태변화 (i행j열에 p를 씀)
row_check[i][p] = False # 행 상태변화 (i행에서 숫자p 쓰기 더이상 불가능)
col_check[j][p] = False # 열 상태변화 (j열에서 숫자p 쓰기 더이상 불가능)
box_check[(i//3)*3+j//3][p] = False # 박스 상태변화 (i행j열 칸에 숫자p 쓰기 더이상 불가능)
backtracking(k+1) # 다음!
board[i][j] = 0 # 스도쿠판 원상복구 (i행j열에 아무것도 없음)
row_check[i][p] = True # 행 원상복구 (i행에서 숫자p 쓰기 가능)
col_check[j][p] = True # 열 원상복구 (j열에서 숫자p 쓰기 가능)
box_check[(i//3)*3+j//3][p] = True # (i행j열 칸에 숫자p 쓰기 가능)
board = []
for _ in range(9):
row = input().strip()
board.append([int(r) for r in row])
zero = []
row_check = [[True]*10 for _ in range(9)]
col_check = [[True]*10 for _ in range(9)]
box_check = [[True]*10 for _ in range(9)]
for i in range(9):
for j in range(9):
if board[i][j] == 0:
zero.append((i,j))
else:
row_check[i][board[i][j]] = False
col_check[j][board[i][j]] = False
box_check[(i//3)*3+j//3][board[i][j]] = False
backtracking(0)백트래킹 시간복잡도 줄이기
1. 꼭 필요한 곳만 방문하기
처음에는 스도쿠 숫자가 이미 채워져있는 칸도 백트래킹에 넣고 별다른 작업 없이 바로 다음 칸으로 넘어가는 식으로 짰었는데, 이건 시간초과가 날 만 했다. 인정.
❗주어진 값들 중에서 백트래킹이 필요한 부분만 방문할 것❗
2. 효율적으로 유망한지 판단하기
예를 들어 유망한지 확인하기 위해 1번 과정, 2번 과정, 3번 과정을 거쳐야 한다고 치자. (여기서는 1번-행탐색, 2번-열탐색, 3번-박스탐색)
그러면 모든 과정에서 1,2,3번을 다 확인할 필요 없이 1번 먼저 확인하고, 1번을 통과하면 2번을 확인하고, 2번을 통과하면 3번을 확인하고, 3번을 확인하면 된다.
또한 과정 중에서도 아니다 싶으면 이후 탐색은 종료하고 바로 나올 수 있도록 해야한다.
def check():
1번 과정 실행
-> 아니다 싶으면 바로 return False
1번 과정에서 안걸러졌으면 2번 과정 실행
-> 아니다 싶으면 바로 return False
2번 과정에서 안걸러졌으면 3번 과정 실행
-> 아니다 싶으면 바로 return False
return True
if check():
~def check1():
1번 과정 실행
-> 아니다 싶으면 바로 return False
return True
def check2():
2번 과정 실행
-> 아니다 싶으면 바로 return False
return True
def check3():
3번 과정 실행
-> 아니다 싶으면 바로 return False
return True
if check1() and check2() and check3(): # 앞에서 False가 나오면 뒤는 아예 실행 X
~3. 자식노드 잘 구하기 ⭐
pypy3 통과 코드와 파이썬 통과 코드의 가장 큰 차이점이 여기였던 거 같다.
- 내가 한 방식 : 1~9까지 모두 체크하면서 유망하다고 판단된 숫자를 사용한다.
- 파이썬 통과하려면 : 애초에 유망한 노드만 가져와서 바로바로 백트래킹을 한다.
처음에 사실 유망한 노드만 가져오는 방식으로 했었는데, 그때는 잘못된 방식으로 해서 시간초과가 났다. (직접 셈..)
유망한 노드도 백트래킹의 성질을 적용해 상태변화<->원상복구 흐름을 잘 태우면 효율적으로 사용할 수 있다. 말로는 설명이 어려우니 위 코드 참고.
배열은 인덱스를 알면 O(1)의 시간복잡도로 빠르게 접근할 수 있으므로 이를 활용해 Boolean 배열로 관리한다.
4. 백트래킹에서 경로 하나만 찾고 끝내기
exit()함수 사용하기 (지양)
if 정답:
exit()프로그래머스에서는 함수로 구현해야하기 때문에 이 방법으로 종료하면 에러가 난다.
- flag 사용하기 (O)
if isEnd:
return
if 정답:
isEnd = True
return flag는 꼭 전역변수로 설정해야 제대로 종료된다.
