백준 1941 소문난 칠공주

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

가장 먼저 배열이 5x5란점이 눈에 띄었다.
5x5 배열에서 브루트포스를 할 수도 있겠다라는 마음가짐으로 문제를 읽었다.

결국 25개중에 7개를 골라야 하는데 25C7은 480700로 해당 가지수를 모두 확인해도 시간초과가 날것이라 생각을 안했다.

dfs로 0~25중 7개를 골랐다면 다음 로직을 짜면 된다.

• 뽑은 7개중 S가 4개 이상인지?
• 뽑은 7개가 모두 인접한지?

S가 4개이상인지 확인하는 로직은 간단하고, 7개가 모두 인접한지 확인하기 위해서는 bfs를 돌려 인접한 칸이 7개인지 확인하면 된다.

from collections import deque
arr = []
for i in range(5):
    arr.append(list(input()))
dx = [-1,0,1,0]
dy = [0,1,0,-1]
p = [0]*25
ans = 0
def dfs(idx,cnt):
    global ans
    if cnt == 7:
        # print(p)
        if checkS():
            if bfs():
                ans += 1
        return
    for i in range(idx,25):
        if not p[i]:
            p[i] = 1
            dfs(i,cnt+1)
            p[i] = 0
def checkS():
    cnt = 0
    for i in range(25):
        if p[i]:
            r = i // 5
            c = i % 5
            if arr[r][c] == 'S':
                cnt += 1
    if cnt >= 4:
        return True
    else:
        return False
def bfs():
    cnt = 0
    checked = [[0]*5 for i in range(5)]
    q = deque([])
    for i in range(25):
        if p[i]:
            r = i // 5
            c = i % 5
            checked[r][c] = 1
            if len(q) == 0:
                q.append((r,c))
    visited = [[0]*5 for i in range(5)]
    while q:
        x,y = q.popleft()
        visited[x][y] = 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= 5 or ny < 0 or ny >= 5 or not checked[nx][ny] or visited[nx][ny]:
                continue
            visited[nx][ny] = 1
            q.append((nx,ny))
    for row in visited:
        cnt += sum(row)
    if cnt == 7:
        return True
    else:
        return False

dfs(0,0)
print(ans)