[알고리즘] BOJ 1941 소문난 칠공주 #Python

김상현·2022년 10월 18일

목록 보기

213/301

[BOJ] 1941 소문난 칠공주 바로가기

📍 문제

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

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

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

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

📍 입력

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

📍 출력

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

📍 풀이

💡 고찰

처음에는 combinations() 함수를 통해 25C7 크기의 조합을 구한 후 해당 조합이 모두 연결되어 있는지 확인한 후 연결되어 있다면 해당 조합이 소문난 칠공주를 결성할 수 있는지 탐색하는 방식을 이용하였다.
코드를 작성한 후 실행해본 결과 시간이 너무 오래 걸려서 다른 방법을 찾아야 했고, 백 트래킹(Back Tracking) 방법을 이용하여 문제를 해결할 수 있었다.
백 트래킹을 이용한 문제 접근은 가지치기를 잘해야 필요 없는 연산을 제외할 수 있다.
참고한 사이트 : [백준] 1941 소문난 칠공주 python

📌 문제 풀이

✏️ 1. '소문난 칠공주'를 결성한 경우를 저장할 집합(set) 자료구조 생성

cases = set()

✏️ 2. '소문난 칠공주'를 결성한 경우를 탐색하기 위한 DFS 함수

def dfs(case, depth, cntY):
    if cntY > 3:
        return
    if depth == 7:
        cases.add(tuple(sorted(case)))
        return
    for x, y in case:
        for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
            nx, ny = x + dx, y + dy
            if nx < 0 or nx > 4 or ny < 0 or ny > 4 or (nx,ny) in case: continue
            if table[ny][nx] == 'Y':
                dfs(case + [(nx,ny)], depth + 1, cntY + 1)
            else:
                dfs(case + [(nx,ny)], depth + 1, cntY)

cntY 는 현재 조합(case)에 존재하는 임도연파의 인원을 의미한다.
- 만약 cntY 의 값이 3 초과 즉, 7명 중 4명 이상인 과반수라면 해당 조합은 소문난 칠공주 에 해당하지 않으므로 진행을 멈춘다.
```
if cntY > 3:
    return
```

depth 는 현재 조합(case)에 인원 수를 의미한다.
- 만약 depth의 값이 7 즉, 소문난 칠공주 에 해당한다면 해당 조합(case)은 '소문난 칠공주'를 저장할 집합 자료구조(cases)에 저장한다.
```
if depth == 7:
    cases.add(tuple(sorted(case)))
    return
```
현재 조합(case)의 각 원소의 상하좌우 값에 해당하는 원소를 추가하여 다시 dfs 함수를 실행한다.
- 만약 해당 원소의 상하좌우 값에 해당하는 값이 현재 조합(case)에 해당하거나 정사각형 격자에서 벗어난다면 해당 경우는 제외한다.
```
if nx < 0 or nx > 4 or ny < 0 or ny > 4 or (nx,ny) in case: continue
```
- 만약 추가하는 원소의 값이 임도연파의 인물(Y)이라면 cntY 의 값을 1증가시켜서 dfs() 를 실행한다.
```
if table[ny][nx] == 'Y':
    dfs(case + [(nx,ny)], depth + 1, cntY + 1)
```
- 반대로 추가하는 원소의 값이 이다솜의 인물(S)이라면 depth 의 값만 1 증가시켜서 dfs() 를 실행한다.
```
else:
    dfs(case + [(nx,ny)], depth + 1, cntY)
```

✏️ 3. dfs() 시작점 찾기

for y in range(5):
    for x in range(5):
        if table[y][x] == 'S':
            dfs([(x,y)], 1, 0)

정사각형 격자에서 현재 위치(x, y)가 이다솜파 인원(S)이라면 현재 위치값을 담은 배열(case)은 [(x,y)] 의 값을, 현재 조합의 인원수(depth)에는 1 의 값을, 현재 조합에 존재하는 임도연파의 인물 수(cntY)에는 0의 값을 할당하여 dfs()를 실행한다.

✍ 코드

from sys import stdin

def solution(table):
    cases = set() # ‘소문난 칠공주’ 결성 cases

    def dfs(case, depth, cntY):
        # 임도연파 학생이 과반수 이상일 경우
        if cntY > 3:
            return

        # 7명의 구성이 완성되었을 경우
        if depth == 7:
            cases.add(tuple(sorted(case)))
            return

        # 모든 경우의 수를 탐색(dfs)
        for x, y in case:
            for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
                nx, ny = x + dx, y + dy
                if nx < 0 or nx > 4 or ny < 0 or ny > 4 or (nx,ny) in case: continue
                if table[ny][nx] == 'Y':
                    dfs(case + [(nx,ny)], depth + 1, cntY + 1)
                else:
                    dfs(case + [(nx,ny)], depth + 1, cntY)
    
    for y in range(5):
        for x in range(5):
            if table[y][x] == 'S':
                dfs([(x,y)], 1, 0)
        
    return len(cases)

table = [list(stdin.readline().strip()) for _ in range(5)]
result = solution(table)
print(result)