[백준/dfs] 1941번: 소문난 칠공주

-문제:https://www.acmicpc.net/problem/1941

1941번: 소문난 칠공주

꽤 쉬운 문제라고 생각했는데 찾아보니 그리 쉽지 않은 문제라서 추가로 공부를 해야할 것 같다

참고한 블로그 

 

전형적인 백트래킹 문제이고, 조합으로 접근하는 문제다

 

dfs함수로 25개의 칸에서 7개의 칸을 선택하는 조합을 구현한다 

0부터 24까지의 숫자를 5*5행렬의 좌표로 변환해주며 탐색한다( 23번은 4행 3열에 위치해있다)

해당 위치가 'Y'이면 ycnt+1하며 재귀로 넘겨주고, 'S'라면 그냥 인자를 그대로 넘긴다 

depth도 사용하지 않고, ycnt도 사용하지 않고 인덱스만 넘기는 경우가 있어서(이런 경우가 어떻게 있지?) dfs(depth,ycnt,idx+1)을 추가한다

백트래킹으로 Y를 4번 이상 만났다면 return하여 가지치기를 함으로써 어느정도 거를 수 있다. 밑에서 ycnt>=4인 경우다.

(가지치기가 무엇?) 위 상황말고도 탐색할 숫자가 나의 남은 선택 수보다 작으면 가지치기를 해준다

 

 

check함수를 통해 7개의 자표들이 서로 연결된 좌표인지 확인한다

0-24까지의 숫자를 5*5행렬 위치로 변환하고, 4방향 탐색을 통해 갈 수 있는 곳의 숫자가 현재 조합 숫자에 포함된 숫자라면 

재귀를 돌린다 

매 조합의 경우마다 visit와 available 변수를 초기화해줘야 한다

available==7인 경우는 7개의 위치 좌표가 서로 연결된 것이므로 result+=1을 해준다 

-정답풀이: 

nextNum+= nr*5+nc로 써서 계속 UnboundLocalError 발생해서 고생했다,,

from sys import stdin
input=stdin.readline
dr=[-1,1,0,0]
dc=[0,0,-1,1]

def check(num):
    global available 
    r=num//5
    c=num%5
    for i in range(4):
        nr,nc=r+dr[i],c+dc[i]
        if 0<=nr<5 and 0<=nc<5 and not visit[nr][nc]:
            nextNum=nr*5+nc
            if nextNum in p:
                visit[nr][nc]=1
                available+=1
                check(nextNum)
                
#깊이, Y의 갯수, 사용할 숫자 인덱스                 
def dfs(depth,ycnt,idx):
    global result,available,visit
    if ycnt>3 or 25-idx <7-depth: #가지치기 
        return 
    if depth==7:
        available=1
        visit=[[0]*5 for _ in range(5)]
        sr,sc=p[0]//5,p[0]%5
        visit[sr][sc]=1
        check(p[0])
        if available ==7:
            result+=1
        return 
    r=idx//5
    c=idx%5
    
    if A[r][c]=='Y':
        p.append(idx)
        dfs(depth+1,ycnt+1,idx+1)
        p.pop()
    else:
        p.append(idx)
        dfs(depth+1,ycnt,idx+1)
        p.pop()
    dfs(depth,ycnt,idx+1)
    
A=[input().rstrip() for _ in range(5)]
visit=[[0]*5 for _ in range(5)]
result=0
p=[]
dfs(0,0,0)
print(result )