문제 링크 : https://www.acmicpc.net/problem/9663
백 트래킹 well-known 문제.
- N * N 모양의 체스 판에, N 개의 퀸을 서로 공격할 수 없는 위치에 배치하는 방법의 개수를 찾는 문제다.
처음에 틀린 이유 - 퀸의 배치는 combination으로 생각해야 하는데, permutation으로 답을 구했기 때문였다.
import sys N = int(sys.stdin.readline()) answer = 0 direction = [(1, 0), (0, 1), (1, 1), (1, -1)] queens = [] def dfs(trace, ban): print(trace) global answer if len(trace) == N: s = '' for x, y in sorted(trace): s += str(x) + str(y) if s not in queens: queens.append(s) print(queens) answer += 1 return #print(trace) for x in range(N): for y in range(N): #print(x, y) if (x, y) not in ban: tempBan = set() trace.append((x, y)) tempBan.add((x, y)) for d in direction: for i in range(-N, N+1): nx = x + d[0]*i ny = y + d[1]*i if 0 <= nx < N and 0 <= ny < N: tempBan.add((nx, ny)) dfs(trace, ban | tempBan) trace.pop() dfs([], set()) print('answer', answer)
그래서 queens 라는 리스트를 선언했고, trace를 문자열 형태로 타입 변경해서 집어넣어 중복을 제거했다. (permutation -> combination). 결론부터 말하면, 이건 답은 내지만 시간 효율이 진짜 안좋은 코드다.
왜 시간초과가 나지 고민하다가 결국 알아내지 못하고 잤다. 근데 자면서 생각하다가 문득 "어 이거 아니야?" 생각이 들어 일어나서 다시 풀어봤다. 현재 시각 04:45 am..
백트래킹 개념을 이해할 때는 State Space Tree (상태 공간 트리) 를 그려보는게 기본이라고 어디선가 들은 것 같다. SST를 그려보니 진짜로 이유를 찾게 됐다.
위의 시간초과 코드1의 상태 공간 트리다. 이 트리는 문제의 핵심을 반영하지 않았다.
핵심 : Queen은 같은 행의 어디든지 이동 할 수 있는데 이를 다르게 말하면, 한 행에는 반드시 하나의 Queen만이 존재해야 한다는 뜻이다.
그렇기 때문에 start 밑의 자식 노드 들이 (0,0) ~ (7,7) 로 뻗어나갈 필요가 없다. depth 1에서는 (0,0) ~ (0,7) depth2 에서는 (1,0) ~ (1,7) ... 이런식으로 트리를 뻗어나간다면 상태 공간 트리의 공간이 훨씬 작아지게 된다.
개선된 state space tree.
import sys N = int(sys.stdin.readline()) answer = 0 direction = [(1, 0), (0, 1), (1, 1), (1, -1)] def dfs(row, trace, ban): global answer if len(trace) == N: answer += 1 return for y in range(N): if (row, y) not in ban: tempBan = set() trace.append((row, y)) tempBan.add((row, y)) for d in direction: for i in range(-N, N + 1): nx = row + d[0] * i ny = y + d[1] * i if 0 <= nx < N and 0 <= ny < N: tempBan.add((nx, ny)) dfs(row + 1, trace, ban | tempBan) trace.pop() dfs(0, [], set()) print(answer)
dfs 매개 변수에 row를 추가해주고, row를 한 칸씩 내려가며 dfs 탐색을 진행했다. 개인적으로 horizontal, vertical, diagonal의 방향을 리스트에 담고 순회하는 저 로직이 직관적이라서 내 맘에 들었는데, len(direction) * (2N) 의 연산이 쓸데없이 많이 필요해서 시간초과가 났다.
import sys N = int(sys.stdin.readline()) answer = 0 def dfs(x, trace): # x는 현재 행 global answer if len(trace) == N: answer += 1 return for y in range(N): check = True for row, col in trace: # 같은 열 제외 if y == col: check = False break # 대각선 제외 if abs(x-row) == abs(y-col): check = False break if check: trace.append((x, y)) dfs(x+1, trace) trace.pop() dfs(0, []) print(answer)
최적화의 최적화. 효율성 테스트도 통과하게 됐다. 시간복잡도와 공간복잡도가 개선됐다. 2차원 리스트에서 Queen이 움직인다는 성질 때문에, 대각은 두 좌표의 차로 구할 수 있었다. 절댓값 함수 abs를 활용했다.