[백준] 소문난 칠공주

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

1941번: 소문난 칠공주

완전 탐색 문제입니다. 저는 조합 + 깊이 우선 탐색을 통해 해결하였습니다. 먼저, 좌표의 조합을 구해줍니다. 구해주는 과정에서 도연파가 4명을 넘어가는 경우는 가지치기를 해줍니다. 만약, 칠공주가 완성되면 칠공주가 인접해있는지를 판별해주어야하는데 이를 dfs로 체크해주었습니다. 칠공주가 위치한 곳을 visited[y][x] = true로 만들어주고 dfs로 탐색하면서 false로 바꾸었습니다. 탐색한 좌표의 개수가 7이면 서로 인접해있는 경우이고 그렇지 않으면 인접해있지 않으므로 칠공주를 만들 수 없는 경우입니다.

 

import sys
from collections import deque

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = 5

board = [
    list(input().rstrip())
    for _ in range(n)
]

ans = 0

dys = [0, 1, 0, -1]
dxs = [1, 0, -1, 0]

def inRange(y, x):
    return 0 <= y < n and 0 <= x < n

def canMakeSeven():
    visited = [
        [False] * n
        for _ in range(n)
    ]

    for y, x in pos:
        visited[y][x] = True

    stack = [pos[0]]

    visited[pos[0][0]][pos[0][1]] = False

    cnt = 1

    while stack:
        y, x = stack.pop()

        for dy, dx in zip(dys, dxs):
            ny = y + dy
            nx = x + dx

            if inRange(ny, nx) and visited[ny][nx]:
                visited[ny][nx] = False
                cnt += 1
                stack.append((ny, nx))

    return True if cnt == 7 else False


# 칠공주들의 위치
pos = []

def combi(start, doyeon, dasom):
    global ans

    #print(start, doyeon, dasom)
    # 도연파가 4명을 넘으면 안된다.
    if doyeon >= 4:
        return

    # 칠공주가 완성된 경우
    if doyeon + dasom == 7:
        if canMakeSeven():
            ans += 1

        return

    for i in range(start, n * n):
        r, c = i // n, i % n

        pos.append((r, c))
        if board[r][c] == 'Y':
            combi(i + 1, doyeon + 1, dasom)
        else:
            combi(i + 1, doyeon, dasom + 1)

        pos.pop()


combi(0, 0, 0)

print(ans)