백준1941 ) 소문난 칠공주👩🏼‍🦰 python

롤이 재미 없고 심심해서 오랜만에 한 문제 풀어봤다. ps 실력은 오랜 시간 꾸준히 키워야 성장하는데 하락은 한 순간이다. 스키 타는 기분

백트래킹 문제인데 가지치기 효과가 클 것 같은 느낌이 들었다. 쌩으로 돌렸을 때 시간초과가 나는 지는 모르겠음. 아니 근데 왜 상대편도 내편이 되는지는 잘 모르겠음.

가지치기

1. Y가 S보다 많아지는 순간 dfs 종료, Y개수만 저장해서 인자로 계속 넘김
2. 선정해야하는 칠공주가 해당 dfs 에서 가지 못한 나머지 칸들보다 많으면 종료

좀 더 클린한 코드

• 5x5 배열을 계속 이용하지말고 1차원 arr[25] 로 하면 좀 더 깔끔하고 코드 짜기 쉽다.
  y = idx//5
  x = idx%5
  이런 식으로 나중에 인접 체크시 사용할 수 있음.
• 칠공주의 조합도 visit 에 하나씩 체크하는 방식이 아닌 1~25까지의 배열에서 숫자 7개의 조합을 구하는 방식으로 하면 좀 더 수월함. bigO는 같아도 기분은 좋다 깔끔하니까
• 칠공주가 연속되어 있어야 한다는 말은 한 명을 시작으로 공주가 있는 방향으로만 진행되는 dfs를 한 번 돌렸을 때 7명 공주가 전부 발견되어야 한다는 뜻. 밑의 check function에 해당되는 부분이다.

arr = [input() for i in range(5)]

prin = [[0 for i in range(5)] for j in range(5)]

diry = [1,-1,0,0]
dirx = [0,0,1,-1]

visit = [[0 for i in range(5)] for j in range(5)]
ans = 0
p = []

def check(s):
    global visit
    y = s//5
    x = s%5
    
    for i in range(4):
        ty = y+diry[i]
        tx = x+dirx[i]
        
        if ty>=0 and ty<5 and tx>=0 and tx<5:
            if visit[ty][tx]==0:
                if (ty*5+tx) in p:
                    visit[ty][tx] = 1
                    check((ty*5+tx))
    
    
            
def dfs(cnt,idx,yn):
    global ans
    global visit
    
    if yn>=4 or 25-idx<7-cnt:
        return
        
    if cnt==7:
        
        check(p[0])
        if sum(sum(visit,[]))==7:
            ans+=1 
        visit = [[0 for i in range(5)] for j in range(5)]
        return
    
    y = idx//5
    x = idx%5
    
    p.append(idx)
    if arr[y][x]=='Y':
        dfs(cnt+1,idx+1,yn+1)
    else:
        dfs(cnt+1,idx+1,yn)
    
    p.pop()
    dfs(cnt,idx+1,yn)
    
dfs(0,0,0)
print(ans)