[백준/G3]소문난칠공주

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

 

 

 

조합,순열,백트래킹 문제

divmod라는 함수로 1차원 인덱스를 2차원 좌표로 만들어주면

편하게 접근이 가능하다.

 

selected[i]는 i번째 선택된 칸의 좌표 (x,y) 튜플을 의미한다.

 

import sys,math
from collections import deque
input= sys.stdin.readline

li=[] 

for _ in range(5):
    str_line= input().rstrip()
    li.append(list(str_line)) 

ans=0

def check(str):
    cnt=0
    for i in str:
        if i=='S':
            cnt+=1
    return cnt>=4

def isconnected(selected):
    q=deque()
    q.append(0)
    visit=[False] *[7]
    visit[0]=True
    cnt=1

    while q:
        cur = q.popleft()
        curX,curY=selected[cur]

        for i in range(1,7):
            if not visit[i]:
                tarX,tarY=selected[i]
                if abs(curX-tarX) + abs(curY-tarY)==1:
                    visit[i]=True
                    q.append(i)
                    cnt+=1
    return cnt==7

def dfs(idx,cnt,str,selected):
    global ans
    if cnt==7:
        if check(str) and isconnected(selected):
            ans+=1
        return

    for i in range(idx,25):
        r,c=divmod(i,5)
        selected[cnt]=(r,c)
        dfs(i+1,cnt+1,str+li[r][c],selected)

selected = [0] * 7
dfs(0,0,"",selected)
print(ans)