[BOJ_Python]1941. 소문난 칠공주

문제

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

 

사용 알고리즘

BFS, Backtracking, BruteForce

 

풀이

고려사항

1. 인원 7명 모으기

2. 이다솜파(S)의 수가 4이상인지 확인

3. 모인 7명의 인접여부 확인

 

후기

1. 이 문제의 keypoint는 학생을 인덱스화하여 백트레킹을 진행하는 것이다.

idx = [(i, j) for j in range(5) for j in range(5)]

인덱스화를 하여 지금 위치 이후 학생들을 기준으로 재귀를 진행했고

이 방식을 사용하면 동일한 학생 집단의 중복이 없다.

처음에 다른 방식으로 한 학생을 기준으로 잡고 7명을 모은 경우

다른 학생을 기준으로 7명을 잡은 경우와 중복되어 동일한 집단이 겹치는 경우가 발생했다.

이것을 확인하는 것에 시간이 많이 사용되어 시간초과를 초래할 수 있어

이러한 중복이 발생되지 않도록 인덱스 방식을 선택하였다.

2. 또한,인접여부 확인 전 이다솜파의 수를 확인을 먼저 진행하도록 하여 상대적으로 무거운 인접여부 작업 횟수를 줄였다.

3. bfs의 경우 방문 리스트를 따로 두어

bfs를 모두 마쳤을 때 7군데 모두 방문여부를 확인하였다.

 

코드

import sys
from collections import deque

input = sys.stdin.readline

didj = [(0, 1), (1, 0), (0, -1), (-1, 0)]


def bfs(members):

    visited = [False for _ in range(7)]

    q = deque([members[0]])

    while q:
        ci, cj = q.popleft()
        for di, dj in didj:
            ni, nj = ci + di, cj + dj
            if 0 <= ni < 5 and 0 <= nj < 5:
                for i in range(7):
                    if visited[i] == False and (ni, nj) == members[i]:
                        visited[i] = True
                        q.append((ni, nj))
	
    # 7명 모두 방문했는지 확인(인접여부)
    if visited.count(False) == 0:
        return True
    return False


# 7명 모으기 위한 재귀 진행
def group(members, depth):

    global cnt

    # 7명 모인 경우 소문난 칠공주 결성 여부 확인
    if len(members) == 7:
        # 이다솜파가 4명 이상인지 확인
        s = 0
        for i, j in members:
            if students[i][j] == "S":
                s += 1
        if s < 4:
            return
        # 인접여부 확인
        if bfs(members):
            # 모두 확인 된 경우 cnt 1 증가
            cnt += 1
        return

    for cur in range(depth, 25):
        members.append(idx[cur])
        group(members, cur + 1)
        members.pop()
    return


students = [list(input()) for _ in range(5)]

# 위치를 찾기 쉽게 인덱스화
idx = [(i, j) for j in range(5) for i in range(5)]

cnt = 0
members = []

group(members, 0)
print(cnt)

 

결과