2024년 1월 2일 알고리즘 문제풀이
문제
난이도
Lv.2
코드
그 어렵다고 소문난 N-Queen 문제. 정글 때 공부했던 문제였는데 그새 까먹었나보다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
def solution(n):
answer = 0
def check_width_row(p,q,arr):
for i in range(n):
if arr[i][q] == '0':
arr[i][q] = False
if arr[p][i] == '0':
arr[p][i] = False
def check_right_down(p,q,arr):
i = 0
while p+i >= 0 and p+i < n and q+i >= 0 and q+i < n:
if arr[p+i][q+i] == '0':
arr[p+i][q+i] = False
i += 1
def check_left_up(p,q,arr):
i = 0
while p+i >= 0 and p+i < n and q+i >= 0 and q+i < n:
if arr[p+i][q+i] == '0':
arr[p+i][q+i] = False
i -= 1
def check_right_up(p,q,arr):
i = 0
while p-i >= 0 and p-i < n and q+i >= 0 and q+i < n:
if arr[p-i][q+i] == '0':
arr[p-i][q+i] = False
i += 1
def check_left_down(p,q,arr):
i = 0
while p+i >= 0 and p+i < n and q-i >= 0 and q-i < n:
if arr[p+i][q-i] == '0':
arr[p+i][q-i] = False
i += 1
def check(p,q,arr):
check_width_row(p,q,arr)
check_right_down(p,q,arr)
check_right_up(p,q,arr)
check_left_up(p,q,arr)
check_left_down(p,q,arr)
arr[p][q] = True
def search(x,arr):
for i in range(n):
if arr[x][i] == '0':
check(x,i,arr)
flag = True
break
else:
flag = False
return flag
for i in range(n):
w = [['0' for _ in range(n)] for _ in range(n)]
w[0][i] = True
check(0,i,w)
k = 1
while k < n:
tmp = search(k,w)
if tmp:
k += 1
else:
break
if k == n:
print(w)
answer += 1
return answer
보드판을 string ‘0’을 배치시켜 만들었다. 원래 숫자로 넣었는데 False일 떄와 0일때가 같이 취급되어서 따로 만들었다. 아무 선택되지 않은 좌표는 ‘0’, 공격당할 수 있기 때문에 놓을 수 없는 곳은 False, 퀸이 위치한 곳은 True로 설정하였다. 우선 임의의 좌표 (p,q)에 퀸을 놓았을 때 퀸이 공격할 수 있는 곳을 False 처리하는 코드를 작성했다. 임의의 좌표의 좌 우 대각선을 바꿔주는 함수를 각각 만들고 하나의 함수로 합쳤다(check). search는 특정 행에서 퀸을 놓을 수 있는 열을 찾아 존재하면 boolean값을 반환해주는 함수이다.
(0,0)부터 (0,n-1) 까지 퀸을 놓으면서 생길 수 있는 경우의 수를 세면 된다고 생각했지만 오답처리되었다. 이유를 생각해봤는데 0행에서 퀸의 위치가 같더라도 다른 배열이 존재할 수 있기 때문이다. 예를 들어, 조건을 만족하는 배열 중에 (0,3)에 퀸이 존재하는 경우의 수가 1개라는 보장이 없다. 하지만 내가 작성한 코드에선 이 경우를 간과했다.
이 부분을 어떻게 해결할까 고민하다가, BFS를 사용하는게 맞다고 생각했다. (0,0)에 퀸을 두고 이때 1행에서 갈 수 있는 모든 경우를 탐색하는 방식을 선택하면 위 문제릃 해결할 수 있을 것 같다. 따라서 0행 k열에 퀸을 두고, 둘 수 없는 곳을 False처리 한다음 1행 중에 가능한 경우를 모두 큐에 담아야 한다. 이후 하나씩 꺼내면서 1행의 해당 열에 다시 퀸을 두고, 이 떄 2행에서 가능한 곳의 좌표를 큐에 담는 방식으로 진행하면 될 것 같다. 단 매번 전체 보드판이 달라지기 때문에 좌표와 보드를 함께 담는게 좋을 것 같다. 하지만 굳이 이전 행에서 몇번째 열에 퀸이 있는지는 알 필요가 없다. 이미 board를 통해 알 수 있으니까. 따라서 이제 몇번째 행에 퀸을 놓아야 할지와 board만 큐에 담았다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
from collections import deque
def solution(n):
answer = 0
def check_width_row(p,q,arr):
for i in range(n):
if arr[i][q] == '0':
arr[i][q] = False
if arr[p][i] == '0':
arr[p][i] = False
def check_right_down(p,q,arr):
i = 0
while p+i >= 0 and p+i < n and q+i >= 0 and q+i < n:
if arr[p+i][q+i] == '0':
arr[p+i][q+i] = False
i += 1
def check_left_up(p,q,arr):
i = 0
while p+i >= 0 and p+i < n and q+i >= 0 and q+i < n:
if arr[p+i][q+i] == '0':
arr[p+i][q+i] = False
i -= 1
def check_right_up(p,q,arr):
i = 0
while p-i >= 0 and p-i < n and q+i >= 0 and q+i < n:
if arr[p-i][q+i] == '0':
arr[p-i][q+i] = False
i += 1
def check_left_down(p,q,arr):
i = 0
while p+i >= 0 and p+i < n and q-i >= 0 and q-i < n:
if arr[p+i][q-i] == '0':
arr[p+i][q-i] = False
i += 1
def check(p,q,arr):
check_width_row(p,q,arr)
check_right_down(p,q,arr)
check_right_up(p,q,arr)
check_left_up(p,q,arr)
check_left_down(p,q,arr)
arr[p][q] = True
def search(x,arr):
for i in range(n):
if arr[x][i] == '0':
check(x,i,arr)
flag = True
break
else:
flag = False
return flag
q = deque()
for i in range(n):
board = [['0' for _ in range(n)] for _ in range(n)]
check(0,i,board)
q.append([1,board])
while q:
row, tmp = q.popleft()
if row == n:
answer += 1
continue
for i in range(n):
if board[row][i] == '0':
check(row,i,board)
q.append([row+1,board])
return answer
하지만 백트래킹의 문제가 있다. 큐에 담긴 각 board의 상태는 독립적이어야 하는데 2차원 배열을 백트래킹하기란 쉽지 않았다.. 뭐 할려면 위에 check를 반대로 하면 되지만 너무 비효율적이라고 생각했다. 보통 DFS와 BFS에서 백트래킹은 어떤 변수나 2차원 배열이라도 하나의 값(보통 특정 좌표)만 변할 때 사용했었다는 것을 떠올렸다.
다른 행의 퀸의 좌표를 좀 더 쉽게 나타낼 수는 없을까? 정사각형 좌표기 떄문에 퀸의 위치가 설정되면서 놓을 수 없는 좌표들의 숫자는 규칙이 있을 것이라고 생각했다. (a,b) 에 퀸이 놓이면 놓을 수 없는 곳은 다음과 같다.
- 모든 행의 b+1 번째 열 (행과 열 1부터 시작하고 좌표는 0부터 시작한다. 헷갈리지 말자.)
- 모든 열의 a+1 번째 행
- (a,b)와 행,열의 거리의 절댓값이 같은 곳 (정사각형이므로 행,열은 더하거나 빠지는 값이 같아야 한다.)
이 로직을 이용하면 백트래킹이 수월해져 BFS를 제대로 활용할 수 있다. 길이가 n인 1차원 배열을 이용하자. 원소의 index는 퀸의 행에서 1을 뺸 값이고 원솟값은 퀸의 열에서 1을 뺸 값이다. 예를 들어, 1행 1열, 2행 3열에 퀸이 있다면 [0,2] 로 표현할 수 있다. 이후 3행에서는 앞에 2개의 값으로 인해 놓을 수없는 곳을 확인하는 과정을 거친 후, 놓을 수 있는 곳을 큐에 추가해주면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from collections import deque
def solution(n):
answer = 0
# (a,b)에 퀸이 있을 때 (p,q) 에 퀸을 놓을 수 있는지 검증하는 함수
def check(a,b,p,q):
if p == a or q == b or abs(a-p) == abs(b-q):
return False
return True
q = deque()
for i in range(n):
q.append([1,[i]])
while q:
now, arr = q.popleft()
if now== n:
answer += 1
continue
for i in range(n):
for j in range(len(arr)):
if not check(j,arr[j],now,i):
break
else:
q.append([now+1,arr+[i]])
return answer
그런데 딱 마지막 case에서 시간초과가 난다. 어떻게 하면 탐색하는 경우의 수를 줄일 수 있을까. 현재 k번째 행을 탐색한다고 하면 k번째 행의 1번쨰 열부터 마지막 열까지 모두 검사한다. 이떄 이미 이전에 선택한 열을 제외하도록 하면 경우를 줄일 수 있지 않을까?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from collections import deque
def solution(n):
answer = 0
# (a,b)에 퀸이 있을 때 (p,q) 에 퀸을 놓을 수 있는지 검증하는 함수
def check(a,b,p,q):
if p == a or q == b or abs(a-p) == abs(b-q):
return False
return True
q = deque()
for i in range(n):
visited = [True for _ in range(n)]
visited[i] = False
q.append([1,[i],visited])
while q:
now, arr, visited = q.popleft()
if now== n:
answer += 1
continue
for i in range(n):
if not visited[i]:
continue
for j in range(len(arr)):
if not check(j,arr[j],now,i):
break
else:
visited[i] = False
q.append([now+1,arr+[i],visited])
visited[i] = True
return answer
이래도 마지막 케이스는 시간초과했다.. 결국 내 방식을 포기하고 다른 사람들의 풀이를 봤다.
출처 : 링크
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def dfs(queen, row, n):
count = 0
if n == row:
return 1
for col in range(n):
queen[row] = col
for i in range(row):
if queen[i] == queen[row]:
break
if abs(queen[i]-queen[row]) == row - i:
break
else:
count += dfs(queen, row + 1, n)
return count
def solution(n):
return dfs([0]*n, 0, n)
위 코드를 보면서 아래처럼 내 스타일로 바꿨다. 근데 내것은 여전히 마지막 case에서 시간초과가뜬다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(n):
answer = 0
def dfs(queen, row, n):
count = 0
if n == row:
return 1
for col in range(n):
queen[row] = col
for i in range(row):
if queen[i] == queen[row]:
break
if abs(queen[i] - queen[row]) == row - i:
break
else:
count += dfs(queen, row + 1, n)
return count
answer = dfs([0] * n, 0, n)
return answer
로직은 같은데.. 가설을 세웠다.
- 정답의 경우 로직 함수를 따로 정의한후
solution()함수에서 직접 반환했다. - 나는 함수내에서 정의하였고 정답을 위한 변수를 따로 선언했다.
- 함수 정의 위치와 변수선언에 따라 시간 차이가 발생할 수 있는가?
몇가지 테스트 케이스를 작성했다.
- 외부에서 함수를 정의하고 변수선언 없이 직접 반환 ⇒ 정답 케이스(통과)
- 외부에서 함수를 정의하고 변수선언 하여 반환
- 내부에서 함수를 정의하고 변수선언 없이 직접 반환
- 내부에서 함수를 정의하고 변수선언 하여 반환 ⇒ 나의 케이스(실패)
2번 외부에서 함수를 정의하고 변수선언 하여 반환하는 경우
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def dfs(queen, row, n):
count = 0
if n == row:
return 1
for col in range(n):
queen[row] = col
for i in range(row):
if queen[i] == queen[row]:
break
if abs(queen[i] - queen[row]) == row - i:
break
else:
count += dfs(queen, row + 1, n)
return count
def solution(n):
answer = dfs([0] * n, 0, n)
return answer
결과 : 실패(시간초과)
3번 내부에서 함수를 정의하고 변수선언 없이 직접 반환하는 경우
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(n):
def dfs(queen, row, n):
count = 0
if n == row:
return 1
for col in range(n):
queen[row] = col
for i in range(row):
if queen[i] == queen[row]:
break
if abs(queen[i] - queen[row]) == row - i:
break
else:
count += dfs(queen, row + 1, n)
return count
return dfs([0]*n, 0, n)
결과 : 성공
변수를 선언해서 시간이 초과됐다고 결론을 내렸다.
그럼 변수선언의 차이에 따라 각 테스트마다 시간이 얼마나 걸렸는지 비교해보았다.
변수선언 하지 않고 직접 반환했을 때
| 직접반환 | 변수선언 |
|---|---|
| 0.01ms | 0.00ms |
| 0,01ms | 0.01ms |
| 0.02ms | 0,01ms |
| 0.13ms | 0.14ms |
| 0.58ms | 0.55ms |
| 2.40ms | 4.62ms |
| 11.37ms | 11.33ms |
| 73.86ms | 54.93ms |
| 322.15ms | 268.73ms |
| 1725.68ms | 1544.81ms |
| 9504.24 | 시간초과 |
엥? 테스트 11에서만 시간초과가 뜬다. n이 커질수록 변수 할당으로인한 추가적인 오버헤드가 발생해서 시간차이가 발생한다! 그 이전에 오히려 적은건, 오차범위 내인듯 하다.
결국 정답
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(n):
def dfs(queen, row, n):
count = 0
if n == row:
return 1
for col in range(n):
queen[row] = col
for i in range(row):
if queen[i] == queen[row]:
break
if abs(queen[i] - queen[row]) == row - i:
break
else:
count += dfs(queen, row + 1, n)
return count
return dfs([0]*n, 0, n)
