DFS + 조건
풀이봤냐: O
DFS:
if (답 리스트 길이) == m: # 조건
print(' '.join(map(str,s)))
return
for i in range(1,n+1):
s.append(i)
DFS()
s.pop()
DFS()
해결 방향:
재귀 DFS call -> 1 - 1234 - (1234) 234 ...
for i in range(1,n+1):
i가 append되고
다음 바로 dfs call
다음 탐색을 위햇 pop 필요.
s.pop() = 마지막 원소 제거 = 재귀 호출 이전 상태로 되돌림
1 -> DFS call -> len(s) == m, print & 종료 -> pop() 하고 다시 돌아야 중복순열 선택..
N과 M (4)
이전 방문 노드보다 작은값은 추가하지 않는다.
이 조건을 어디에 추가해야 될까.
내 풀이) -> 출력은 됨. 비효율적 = 역시나 시간초과
길이가 다 나왔을 때 (DFS 경로탐색 후)
정렬되었는지 여부를 검사한다.
정렬된 경우만 출력한다.
원하는 풀이)
탐색 노드보다 탐색 직전 노드가 크면 s에 넣지 않는다.
아. dfs 탐색에서 for i in range(i, n+1)로 넣어주던걸 start부터 넣어주면 된다. start는 dfs의 인자로 제공한다.
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
s = []
def dfs(start):
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(start, n+1):
s.append(i)
dfs(i)
s.pop()
dfs(1)
N-Queen
내 풀이)
마킹)
이차원 리스트에서 퀸을 놓는다.
퀸의 영향을 받는 모든 리스트 부분을 1로 마킹한다.
놓을 수 있는 리스트 위치에 다시 퀸을 놓는다. (재귀)
조건) 퀸 갯수가 N개를 만족하면 정답으로 1개 카운트한다.
=> 이 풀이에서는 Backtracking으로 그래프를 못 되돌림.
시간초과
해설)
v1,v2,v3로 visited가 3방향으로 Queen 존재여부를 검사한다.
row를 한 줄씩 탐색하며 row가 N-1까지 도달하면 ans+=1, 도달하지 못하고 중간에 백트래킹하는 경우, v1,v2,v3를 다시 0으로 돌려놓는다.
dfs(row) -> dfs(row+1) 순으로 탐색 진행
추가로 백트래킹의 조건을 달아주는 것이 아니라, dfs탐색 후 if 조건문에 도달하지 못하면 v1,v2,v3를 다시 0으로 되돌리는 것 자체가 백트래킹임.
3방향을 위에만 보면서 한 줄씩 내려간다는 개념을 떠올리지도 못했다.
나는 십자방향 BFS 문제만 풀어서 퀸도 검사 조건에 8방향을 모두 검사해야 한다고 생각햇다. 하지만 이렇게 가면 비효율적으로 모든 노드를 검사하게 된다.
한 줄에 퀸 하나를 놓고 바로 다음 줄로 넘어가버리면, 가로 줄의 불필요한 검사를 스킵할 수 있다.
퀸의 특성과 visited를 여러개 사용할 수 있다는 점. 백트래킹과 DFS를 이해하기 좋은 기본 문제라고 생각한다.
python 시간초과 이슈
