1941: 소문난 칠공주

문제 링크

1941: 소문난 칠공주

구현 방식

• brute force로 25C7의 경우를 모두 고려해주었다
  • 3번 조건 ['이다솜파'가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 '이다솜파'의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.]에 따라 ratioCheck() 함수로 pruning 해줌
• adjacentCheck 함수를 이용해 가로 세로로 인접해 있는 지를 확인해주었다
  • visit을 [False]*7로 선언해주고, 해당하는 comb의 경우마다 노드 comb[0]에서부터 bfs로 visit의 원소를 모두 True로 바꿀 수 있는 지를 확인해줌 (하나라도 False면 인접하지 않은 경우이고, 모두 True면 인접한 경우)

코드

import sys
from collections import deque
from itertools import combinations

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def ratioCheck(comb):
    y_cnt = 0
    for x, y in comb:
        if board[x][y] == 'Y': y_cnt += 1
    if y_cnt <= 3: return True
    else: return False

def adjacentCheck(comb):
    comb_set = set(comb)
    queue = deque([]); queue.append(comb[0])
    visit = [False]*7; visit[0] = True

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if (nx, ny) in comb_set:
                nidx = comb.index((nx, ny))
                if not visit[nidx]:
                    visit[nidx] = True; queue.append((nx, ny))
    return False if False in visit else True


board = [list(sys.stdin.readline()[:-1]) for _ in range(5)]
pos = [(i, j) for i in range(5) for j in range(5)]; answer = 0
for comb in list(combinations(pos, 7)):
    if ratioCheck(comb): #비율로 pruning
        if adjacentCheck(comb):
            answer += 1
print(answer)