문제

백준 1941번: 소문난 칠공주
https://www.acmicpc.net/problem/1941

풀이💡

처음에 bfs로 풀면서 중복된 경우에 어떻게 처리해야 하는지 몰라서 끙끙 앓았습니다...😱 도저히 혼자서 해결을 못 할 것 같아서 방법을 찾아봤습니다.

핵심은 '조합'을 이용하여 7개의 자리를 뽑기

교실은 5x5로 고정되어 있습니다. 25개의 자리 중 7개를 뽑는 경우의 수는 25C7 = 480700 밖에 되지 않기 때문에 조건에 모두 만족하는 자리만 정답으로 세어주면 됩니다.

다음과 같이 각 25개의 자리에 0~24까지의 번호를 지정하고 문제를 풀겠습니다. (인덱싱을 편하게 하기 위해서 0~24로 정함)

✅ 풀이 순서

1️⃣ 25개의 자리 중에서 7개를 뽑아줍니다.
2️⃣ 뽑힌 자리에 앉은 7명의 학생 중 '이다솜파' 학생이 적어도 4명 이상인지 확인합니다.
3️⃣ 2번 조건을 만족한다면, 7개의 자리가 서로 인접한지 확인합니다. (2번 조건을 만족하지 않으면 바로 continue)
4️⃣ 3번 조건을 만족한다면, answer에 1을 더해줍니다. (answer은 정답을 담는 변수)

bfs 구현 시 주의 사항❗️

bfs를 구현하실 때는 한 가지 주의사항이 있습니다.
v자리가 있을 때, v자리의 상하좌우로 가기 위해 v에서 +-5, +-1를 해주어야 합니다. 이때 1분단과 5분단, 맨 끝에 있는 분단의 자리들에 경우에는 +-1을 해주면 좌우가 아닌 반대쪽 분단으로 넘어갑니다.

12번 자리와 달리, 14번 자리를 보면 상하좌우의 '우'가 없는데 +1를 해주다보니 이상한 자리로 넘어가게 되죠. 따라서 맨 끝 분단에 경우는 제외해줘야합니다.

코드💛

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


def count_s(seven):
    cnt_s, cnt_y = 0, 0
    for x in seven:
        if sy[x // 5][x % 5] == 'S':
            cnt_s += 1
        else:
            cnt_y += 1
            if cnt_y > 3:
                return False
    return True


def bfs(seven):
    visited = [False] * 25
    visited[seven[0]] = True
    q = deque([seven[0]])
    cnt = 0
    while q:
        v = q.popleft()
        cnt += 1
        for w in [v - 5, v - 1, v + 1, v + 5]:
            # w가 맨 왼쪽 자리거나 맨 오른쪽 자리인 경우는 제외
            if (v % 5 == 4 and w == v + 1) or (v % 5 == 0 and w == v -1):
                continue
            if 0 <= w < 25 and w in seven and not visited[w]:
                visited[w] = True
                q.append(w)

    if cnt == 7:
        return True
    return False


sy = [list(input().rstrip()) for _ in range(5)]
answer = 0
# 조합을 이용해 7개의 자리 뽑기
for combi in combinations([i for i in range(25)], 7):
    # 7명 중 '이다솜파' 학생이 적어도 4명 이상인지 확인
    if not count_s(combi):
        continue
    # 7개의 자리가 서로 인접한지 확인
    if bfs(combi):
        answer += 1
print(answer)