[백준 1941] 소문난 칠공주 (Python) / G3

문제

1941. 소문난 칠공주

코드

import sys
input = sys.stdin.readline

from collections import deque

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 연결 확인
def bfs():
    q = deque()
    visited = [[0]*5 for _ in range(5)]
    cnt = 1
    x = girls[0][0]
    y = girls[0][1]
    visited[x][y] = 1
    q.append((x, y))

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < 5 and 0 <= ny < 5 and not visited[nx][ny]:
                if [nx, ny] in girls:
                    cnt += 1
                    visited[nx][ny] = 1
                    q.append((nx, ny))
    if cnt == 7:
        return True
    else:
        return False


def back(idx, depth, yeon):
    global res
    if yeon >= 4 or 25 - idx < 7 - depth:
        return
    if depth == 7:
        if bfs():
            res += 1
        return

    x = idx // 5
    y = idx % 5
    if board[x][y] == "Y":
        girls.append([x, y])
        back(idx + 1, depth + 1, yeon + 1)
        girls.pop()
    else:
        girls.append([x, y])
        back(idx + 1, depth+1, yeon)
        girls.pop()

    back(idx+1, depth, yeon)



board = [list(input().strip()) for _ in range(5)]
res = 0

girls = []

back(0,0,0)
print(res)

코드 설명

BFS/DFS 문제일것이라 생각해서 보드판에서 7명을 뽑는 것을 DFS처럼 구현했었는데 예제가 답이 다르게 나와서 보니까

.....
SYSYS
.Y...
.S...
.....

이 경우를 탐색을 못하는 문제가 있었다.

백트레킹만 이용해야한다는 것을 파악하고, 5 * 5 보드판을

0  1  2  3  4
5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

로 번호를 매겨서 0~24 중에 숫자 7개를 선택하는 back 함수를 작성하고
7개를 모두 선택하였다면 BFS를 사용하여 7개가 다 이어져있는지를 확인하였다.

백트레킹 가지치기의 조건을 임도연파가 4개 이상 되거나, 남은 골라야하는 숫자 보다 선택할 수 있는 숫자가 커졌을 때 return을 해주었다.