[BOJ] 1941: 소문난 칠공주

문제 링크

Question

총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.

 

위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.

1. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
2. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
3. 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
4. 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.

여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.

Input

'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.

Output

첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.

---

Solution

문제를 두 단계로 나누어서 볼 수 있다.

1. 7명의 여학생 중 4명 이상이 'S'인 위치 조합 구하기
2. 구한 조합이 서로 인접해 있는 위치인지 확인하기

우선적으로, 전체 행렬에서 주어진 조건에 맞는 조합을 구하기 위해 DFS + Backtracking을 이용하였다.

def dfs(board: List[List[str]], start: int, stack: List[str], count_not_S: int):
    if count_not_S >= 4:
        return 0

    if len(stack) == 7:
        return check_available(stack)

    available_count = 0
    for idx in range(start, 25):
        cur_i, cur_j = idx//5, idx%5

        stack.append((cur_i, cur_j))
        available_count += dfs(board, idx+1, stack, count_not_S+int(board[cur_i][cur_j]!='S'))
        stack.pop()
    return available_count

시작 지점인 start로 부터 한 칸씩 순회하며 배열의 행과 열 위치인 cur_i, cur_j를 찾고, Stack에 넣은 후 재귀적으로 DFS를 진행한다. 그 후 Stack에서 다시 빼서 다음 인덱스에 대해 반복하도록 한다.

 

이때, Backtracking을 도입하기 위해서 해당 위치가 S인지 아닌지를 파악해 다음 재귀함수에 넣어주게 된다. 만약 특정 시점에서 S가 아닌 값의 개수가 4 이상이 된다면, 이는 조건을 성립할 수 없으므로 즉시 불가능을 반환하여 시간복잡도를 감소시키고자 하였다.

 

만약 해당 조건을 만족하는 만족하는 위치들의 조합이 나왔을 때, check_available 함수를 통해서 각 위치들이 서로 인접해있는지를 확인해준다. 최종적으로는 모든 가능한 경우의 수를 모아서 Return 해준다.

def check_available(point_list: List[Tuple[int, int]]):
    visited = [False] * len(point_list)
    visited[0] = True
    queue = deque([point_list[0]])

    while queue:
        cur_i, cur_j = queue.popleft()

        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            next_i, next_j = cur_i + di, cur_j + dj
            if not (0<=next_i<5 and 0<=next_j<5):
                continue
            if (next_i, next_j) not in point_list:
                continue

            cur_idx = point_list.index((next_i, next_j))
            if visited[cur_idx]:
                continue
            visited[cur_idx] = True
            queue.append((next_i, next_j))

    if all(visited):
        return 1
    else:
        return 0

7개의 위치를 원소로 가지고 있는 리스트를 입력받아서, 모든 위치들이 서로 인접해있는지를 BFS를 통해서 확인한다.

 

맨 처음 위치에서 이동할 수 있는 네 방향의 인접한 위치가, point_list에 포함되었는지 여부를 확인하여 포함되었을 경우 해당 위치를 방문한 것으로 처리한다.

(해당 과정에서 O(N)의 시간복잡도가 소요되나, 2차원 Visited 배열을 사용하면 O(1)의 시간복잡도로도 가능할 것 같다.)

 

최종적으로 모든 위치에 방문했다면, 이는 모든 원소가 인접해 있다는 것이고 그렇지 않다면 인접하지 않은 원소가 있다는 것이다.

 

전체 정답 코드는 아래와 같다.

import sys
from typing import List, Tuple
from collections import deque
input = lambda: sys.stdin.readline().strip()


def dfs(board: List[List[str]], start: int, stack: List[str], count_not_S: int):
    if count_not_S >= 4:
        return 0

    if len(stack) == 7:
        return check_available(stack)

    available_count = 0
    for idx in range(start, 25):
        cur_i, cur_j = idx//5, idx%5

        stack.append((cur_i, cur_j))
        available_count += dfs(board, idx+1, stack, count_not_S+int(board[cur_i][cur_j]!='S'))
        stack.pop()
    return available_count


def check_available(point_list: List[Tuple[int, int]]):
    visited = [False] * len(point_list)
    visited[0] = True
    queue = deque([point_list[0]])

    while queue:
        cur_i, cur_j = queue.popleft()

        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            next_i, next_j = cur_i + di, cur_j + dj
            if not (0<=next_i<5 and 0<=next_j<5):
                continue
            if (next_i, next_j) not in point_list:
                continue

            cur_idx = point_list.index((next_i, next_j))
            if visited[cur_idx]:
                continue
            visited[cur_idx] = True
            queue.append((next_i, next_j))

    if all(visited):
        return 1
    else:
        return 0


if __name__ == "__main__":
    board = [input() for _ in range(5)]
    answer = dfs(board, 0, [], 0)
    print(answer)