소문난 칠공주 (1941번) - 백준 (BOJ)

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

1941번: 소문난 칠공주

 

 

백준 - 소문난 칠공주 (Rigging the Bovine Election) (1941번)

 

난이도 : Gold 3

알고리즘&자료구조 : Simulation (구현) & Combinations (조합)

 

 

import sys
input = sys.stdin.readline
from itertools import combinations


def _adjs(r, c):
    if 0 < r:  yield r-1, c
    if 0 < c:  yield r, c-1
    if r < 4:  yield r+1, c
    if c < 4:  yield r, c+1


def _is_connected(coords):
    rest = set(coords[1:])
    stack = [coords[0]]
    while stack:
        for r, c in _adjs(*stack.pop()):
            if (r, c) in rest:
                stack.append((r, c))
                rest.remove((r, c))
    return False if rest else True


class Election():
    def __init__(self):
        district = [input().rstrip() for _ in range(5)]
        cnt = 0
        for seq in combinations(((r, c) for c in range(5) for r in range(5)), 7):
            if sum(1 if district[r][c] == 'S' else 0 for r, c in seq) < 4:
                continue
            if _is_connected(seq):
                cnt += 1
        self.answer = cnt


if __name__ == '__main__':
    elec = Election()
    print(elec.answer)

 

 

①  5 * 5 크기의 격자이므로 총 25개의 좌표가 있다.

이 25개의 좌표 중 7개를 임의로 뽑는다. (조합 : 25C7 의 경우의 수)

combinations(((r, c) for c in range(5) for r in range(5)), 7)

 

 

 

② 'S'의 개수가 4개보다 작은지 확인한다.

(4개보다 작으면 안되므로, continue로 빠져나온다.) 

if sum(1 if district[r][c] == 'S' else 0 for r, c in seq) < 4:
    continue

 

 

 

③ 'S'가 4개 이상인 경우, 7개의 각 좌표들이 모두 연결돼있는지 확인한다.

(연결되어있다면, 가능한 경우이므로 cnt에 1을 더해준다.)

if _is_connected(seq):
    cnt += 1

 

 

 

④ 최종적인 cnt 값을 출력한다.