1914번 소문난 칠공주

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

---

아이디어

아이디어 생각해내는 게 너무 어려운 문제였다.
처음에 생각했던 건 칠공주들이 이웃해있어야하니까 해당 칸에서 움직일 수 있는 경우가 오른쪽과 아래쪽이고 이걸 어떻게 처리해야할지 고민을 했었다.

def dfs(n, cnt, s_cnt):
    global answer
    if cnt > 7: return
    if n == 25:
        if cnt == 7 and s_cnt >= 4:
            if bfs():
                answer += 1
        return

    visited[n//5][n%5] = True # 방문처리
    dfs(n+1, cnt+1, s_cnt+int(graph[n//5][n%5]=='S'))
    visited[n//5][n%5] = False # 원상복구
    dfs(n+1, cnt, s_cnt)

모든 경우의 수를 다 보기 위한 코드이다. cnt는 방문한 학생 수이고 s_cnt는 다솜파 학생 수이다. 만약 cnt가 7이고 다솜파 학생수도 4명 이상이면 BFS 함수를 통해서 이웃해있는지 확인한다. 이웃하면 answer += 1

def bfs():
    queue = deque()
    vv = [[False]*5 for _ in range(5)]
    flag = 0
    for i in range(5):
        for j in range(5):
            if visited[i][j]:
                flag = 1
                queue.append((i, j))
                vv[i][j] = True
                break
        if flag: break

    dx = [1, 0, 0, -1]
    dy = [0, 1, -1, 0]
    temp = 1 # 몇 개 이웃해있는지

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y+dy[i]
            if nx >= 5 or ny >= 5 or nx < 0 or ny < 0: continue
            if visited[nx][ny] and not vv[nx][ny] :
                vv[nx][ny] = True
                temp += 1
                queue.append((nx, ny))

    return temp == 7

BFS 함수에서는 방문처리 할 리스트를 하나더 만들어줬다.
그 이유는 visited가 True여서 visited를 False로 만들어버리면 dfs 함수로 다시 갔을 때 충돌이 생긴다. 그래서 독립적인 방문처리 리스트(vv)를 하나 더 만들었다.

---

코드

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

def dfs(n, cnt, s_cnt):
    global answer
    if cnt > 7: return
    if n == 25:
        if cnt == 7 and s_cnt >= 4:
            if bfs():
                answer += 1
        return

    visited[n//5][n%5] = True # 방문처리
    dfs(n+1, cnt+1, s_cnt+int(graph[n//5][n%5]=='S'))
    visited[n//5][n%5] = False # 원상복구
    dfs(n+1, cnt, s_cnt)

def bfs():
    queue = deque()
    vv = [[False]*5 for _ in range(5)]
    flag = 0
    for i in range(5):
        for j in range(5):
            if visited[i][j]:
                flag = 1
                queue.append((i, j))
                vv[i][j] = True
                break
        if flag: break

    dx = [1, 0, 0, -1]
    dy = [0, 1, -1, 0]
    temp = 1 # 몇 개 이웃해있는지

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y+dy[i]
            if nx >= 5 or ny >= 5 or nx < 0 or ny < 0: continue
            if visited[nx][ny] and not vv[nx][ny] :
                vv[nx][ny] = True
                temp += 1
                queue.append((nx, ny))

    return temp == 7

graph = [list(input().rstrip()) for _ in range(5)]
visited = [[False] * 5 for _ in range(5)]
answer, n = 0, 0
dfs(0, 0, 0)
print(answer)