Baekjoon 1941. 소문난 칠공주 / Python

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

문제 요약

5×5의 정사각형 격자에 'S' (이다솜파) 또는 'Y' (임도연파)로 표시된 여학생들이 있다. 이다솜파의 학생 4명 이상을 포함해 7명의 여학생이 가로나 세로로 인접하게 모여 "소문난 칠공주"를 결성할 수 있는 모든 경우의 수를 구하는 문제다.

알고리즘 설명

알고리즘 개요

1. 백트래킹으로 조합 생성: 5×5 격자에서 7명의 여학생을 선택하는 모든 조합을 생성한다.
2. BFS로 인접 확인: 선택된 7명의 여학생이 가로나 세로로 인접해 있는지 BFS로 확인한다.
3. 이다솜파 학생 수 확인: 선택된 7명의 여학생 중 이다솜파 학생이 4명 이상인지 확인한다.
4. 결과 계산: 위 조건을 모두 만족하는 경우의 수를 계산한다.

시간복잡도

• 백트래킹을 통해 25명 중 7명을 선택하는 경우의 수는 25C7이다. 이는 약 480,700가지 경우다.
• 각 경우에 대해 BFS를 수행하는데, BFS의 시간복잡도는 O(7)=O(1)이다. 따라서 전체 시간복잡도는 O(25C7×7) ≈ O(480,700)이다.

코드 설명

1. 입력 처리: 5×5 격자를 입력받아 mate에 저장한다.
2. 방향 벡터 설정: 상하좌우 방향을 나타내는 벡터를 설정한다.
3. bfs1 함수: 선택된 7명이 서로 인접해 있는지 BFS로 확인한다.
4. bfs2 함수: 백트래킹을 사용해 7명의 여학생을 선택하는 모든 조합을 생성하고, 각 조합에 대해 bfs1을 호출해 인접 여부를 확인한다.
5. 메인 루프: 백트래킹을 통해 모든 조합을 확인하고, 조건을 만족하는 경우의 수를 출력한다.

from collections import deque as dq

mate = [list(input()) for _ in range(5)]  # 5x5 격자 입력
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]  # 상하좌우 방향 벡터
res = 0  # 결과를 저장할 변수

# 선택된 7명이 서로 인접해 있는지 확인하는 함수
def bfs1(arr_):
    visit = [[1] * 5 for _ in range(5)]  # 방문 여부 배열
    for i in arr_:  # 선택된 7명의 위치를 0으로 표시
        visit[i[0]][i[1]] = 0

    cnt_tmp = 1  # 인접한 학생 수 카운트
    q = dq([arr_[0]])  # 시작점
    visit[arr_[0][0]][arr_[0][1]] = 1  # 시작점 방문 처리
    while q:
        x, y = q.popleft()
        for dx, dy in direction:  # 네 방향 탐색
            nx, ny = x + dx, y + dy
            if nx in range(5) and ny in range(5):  # 격자 범위 내 확인
                if not visit[nx][ny]:  # 방문하지 않은 곳이라면
                    visit[nx][ny] = 1  # 방문 처리
                    cnt_tmp += 1  # 인접한 학생 수 증가
                    q.append((nx, ny))
    if cnt_tmp != 7:  # 인접한 학생이 7명이 아니면
        return False
    else:
        return True

# 백트래킹으로 조합을 생성하는 함수
def bfs2(length=0, start=0, cnt=0):
    global res
    if cnt >= 4:  # 임도연파의 학생이 4명 이상이면 종료
        return
    if length == 7:  # 7명을 모두 선택한 경우
        if bfs1(arr):  # 인접한지 확인
            res += 1  # 경우의 수 증가
        return
    for i in range(start, 25):  # 백트래킹을 통해 조합 생성
        x, y = i // 5, i % 5
        arr.append((x, y))
        bfs2(length + 1, i + 1, cnt + (mate[x][y] == 'Y'))  # 다음 단계로
        arr.pop()  # 백트래킹을 위한 원상복구

arr = []
bfs2()
print(res)