[Python] 백준 / gold / 1941 : 소문난 칠공주

문제 링크 : https://www.acmicpc.net/problem/1941

내가 정말 DFS의 개념을 정확히 알고있나 한번 더 체크해준 문제. DFS 는 특성상 십자 모양으로 갈라지는 탐색을 하기는 어렵다. 근데 이 문제는 그런 경우를 요구하기 때문에 DFS 로 풀지 않는게 좋다. 근데 왜 이 문제의 분류가 백트래킹이냐. 25C7 의 경우를 나눠야 하기 때문에 그런 것 같다.

먼저 combinations 로 가능한 위치 7개 조합을 뽑은 뒤, 'S' 가 4개 미만이라면 거르고, 원소가 서로 인접해 있는지 BFS 로 체크해서 풀었다.

얻어갈 2가지

1. DFS 탐색으로 십자 모양 갈라지는 탐색은 하기 어렵다.
2. 좌표 튜플을 리스트 컴프리헨션으로 초기화 하는 방법
3. 리스트 원소 타입이 boolean 인 경우는 if False in myList: 같은 문법도 사용할 수 있다.

-> 이런게 십자 모양으로 갈라지는 탐색.

파이썬 코드

from itertools import combinations
from collections import deque
import sys
graph = []
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
positions = [(i, j) for i in range(5) for j in range(5)]
combs = list(combinations(positions, 7))
answer = 0

for _ in range(5):
    graph.append(list(sys.stdin.readline().strip()))


def checkDaSom(givenComb):
    daSom = 0
    for x, y in givenComb:
        if graph[x][y] == 'S':
            daSom += 1
    return True if daSom >= 4 else False


def checkAdjacent(givenComb):
    visit = [False]*7
    q = deque()
    q.append(givenComb[0])
    visit[0] = True

    while q:
        x, y = q.popleft()
        for d in direction:
            nx = x + d[0]
            ny = y + d[1]
            if (nx, ny) in givenComb:
                nextIdx = givenComb.index((nx, ny))
                if not visit[nextIdx]:
                    q.append((nx, ny))
                    visit[nextIdx] = True

    return False if False in visit else True


for comb in combs:
    if checkDaSom(comb):
        if checkAdjacent(comb):
            answer += 1

print(answer)