[백준 9663- N-Queen][파이썬] 백 트래킹, dp -19일차

https://www.acmicpc.net/problem/9663

2가지로 풀이했다. back tracking, dp

 

1. 백 트래킹

key point: is_promising, x==n에 answer+=1

 

is_promising -> 같은 열에 있거나 대각선에 있으면 false를 return 해서 탐색을 하지 x

 

if x==n: answer+=1

-> n번쨰 칸에 닿았을 때 -> 탐색이 완료 되었을 때,

n에 안 닿았을 때는 퀸의 자리를 옮겨가면서 is_promising 로직 실행 후, 재귀적으로 한칸씩 키워서 0 -> 1 ->2 로 탐색 진행

 

--탐색 과정

n=4

x=0

else로 가게 되고

i=0

row[x]=0 (0,0을 의미) -> solution이 커져도 영향을 줌

if is_promosing(0)을 호출

(is_promising 실행 시작)

i=0

if row[x]==row[x] 에 걸려서

return False

(is_promising 실행 끝)

/// False 니까 solution(x+1)로 넘어가는게 아니라 range의 나머지 값들을 진행해준다)

 

i=1,2 3 남았고

row[0]=1, row[0]=2, row[0]=3 으로 모두 실행

->  모두 false 반환

def is_promising 코드에 for문을 다 돌리고 나면 return True를 실행해주는데, 한 줄 다 돌렸으면 다음줄을 돌려라하는 의미

--> if is_promising이 true가 되니까 solution(1) 실행

 

또 else 문에 걸리고

for i in range(4)

row[1]=0 ~ row[1]=4 까지 가능하고

if row[1]==row[0]  -> row[0]=0 으로 설정해두었음으로 false

row[1]=1 이면 대각선에 걸려서 false

row[1]=2 이면 true (3 남겨두고)

solution(3) 실행

 

또 else문에 걸리고

row[3]=0 ~row[3]=4 까지 중에

전부 false

 

solution(4) 실행

 

x==4 라서

answer=1

 

남겨둔 

row[1]=3

false

또 solution(3)실행, solution(4)실행해서

 

answer=2

 

2. dp

key point: visitied 설정하기

 

dfs 로직처럼 visited를 false 와 true 로 나누어서 true 면 -> 탐색 해도 좋은 경우면 solution을 하나 올리고 또 실행