[백준] 1941 소문난 칠공주 (파이썬) (1)

골드 Ⅲ

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

1941번: 소문난 칠공주

 

📄 문제

• 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었다.
• 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었다.
• ‘이다솜파’의 학생들은 ‘소문난 칠공주’를 결성한다.
• ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.
  1. 7명의 여학생들로 구성되어야 한다.
  2. 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
  3. ‘이다솜파’의 학생들로만 구성될 필요는 없다.
  4. 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다.
  5. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.

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

 

---

💡 아이디어

• 총 25명의 여학생 중 7명을 뽑는다.
  
  1. 조합 함수 사용하여 미리 뽑아 놓는다.
  2. 조합 함수를 사용하지 않고 깊이 우선 탐색(DFS)을 활용하여 직접 구현한다.
• 1 ~ 25 중 7개의 숫자를 뽑아 행렬의 위치를 파악한다.
  • 뽑은 숫자를 5로 나눈 몫은 행의 위치가 되고
  • 뽑은 숫자를 5로 나눈 나머지는 열의 위치가 된다. 

• 뽑은 7 명 중 ‘이다솜파’ 학생이 4명 이상 포함되어 있는 지 확인한다.
• ‘임도연파’ 학생이 4명 이상 포함 된 경우에는 탐색을 바로 종료한다.
  • ‘이다솜파’ 학생은 4명 이상 포함되어야 한다.
  • ‘임도연파’ 학생이 4명 이상이면 ‘이다솜파’ 학생은 3명 이하로 포함된다.

• 뽑은 7명의 학생 위치를 새로운 5x5 격자에 표시한다.
• 새로운 격자에 표시된 위치가 서로 인접해 있는지 너비 우선 탐색(BFS)을 활용하여 확인한다.
• 모든 조건을 만족하면 칠공주 경우의 수를 +1 한다.
  1. ‘이다솜파’ 학생이 4명 이상 포함되어야한다.
  2. 뽑힌 7명의 위치가 서로 인접한다.

• 뽑힌 모든 경우의 수를 확인한 뒤 모든 조건을 만족하는 칠공주 경우의 수를 출력한다.

 

---

시간 단축이 가능한 다른 풀이 방법이 존재한다.

5x5 격자를 4방향으로 탐색하면서 모든 조건을 만족하는 7명을 바로 뽑는 방법이 있다. ✅

• ‘이다솜파’ 학생이 4명 이상 존재한다.
• 7명의 위치가 서로 인접한다. 

 

https://bu119.tistory.com/68

[백준] 1941 소문난 칠공주 (파이썬) (2)

 

📝 문제 풀이 (Code)

최종 코드

조합 함수(combinations)를 사용하지 않는다.

• 전체 25중 7명을 뽑는 경우를 깊이우선탐색(DFS) 활용하여 직접 구현한다.
• 7명을 뽑으면서 ‘임도연파’  학생이 4명 이상인지 확인한다.
• ‘임도연파’  학생이 4명 이상이면 ‘이다솜파’ 학생이 3명 이하 이므로 해당 경우는 뽑기를 중단한다.
• 이어서 다른 경우를 뽑는다.

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

# 7명 선택
def dfs(idx, yCnt, memCnt):
    global cnt, members

    # 임도‘연’파가 4이상이면 이다‘솜’파가 4이상 안됨
    if yCnt >= 4:
        return

    # 조건을 만족하는 7명을 뽑으면
    if memCnt == 7:
        # 7명이 인접한 지 확인한다.
        if bfs(members):
            cnt += 1
        return

    for k in range(idx, 25):
        # 숫자를 통해 좌표를 표현한다.
        # 25번 까지 중 행은 번호를 5로 나눈 몫
        ni = k // 5
        # 25번 까지 중 열은 번호를 5로 나눈 나머지
        nj = k % 5
        # 임도‘연’파 변화 저장
        new = yCnt
        if students[ni][nj] == 'Y':
            new += 1
        # 해당 위치를 멤버로 추가
        members.append((ni, nj))
        dfs(k+1, new, memCnt+1)
        # 해당 위치를 제거 (멤버X)
        members.pop()

        
# 7명이 인접해 있는지 확인        
def bfs(members):
    deq = deque()
    # 7공주 방문 체크
    visited = [[1] * 5 for _ in range(5)]

    # 첫 사람부터 탐색 시작
    total = 1
    deq.append(members[0])
    # 방문 위치 제거하고 저장
    for x, y in members[1:]:
        visited[x][y] = 0

    while deq:
        x, y = deq.popleft()

        for k in range(4):
            nx = x + di[k]
            ny = y + dj[k]
            if 0 <= nx < 5 and 0 <= ny < 5 and visited[nx][ny] == 0:
                # 방문 체크
                visited[nx][ny] = 1
                deq.append((nx,ny))
                total += 1
    # 7명 모두 인접
    if total == 7:
        return True
    return False


students = [input() for _ in range(5)]
di = [0,1,0,-1]
dj = [1,0,-1,0]
# 7공주 경우의 수 저장
cnt = 0
# 7공주 멤버 저장
members = []
dfs(0, 0, 0)

print(cnt)

 

처음 코드

조합 함수(combinations)를 사용한다.

• 전체에서 7명을 뽑는다. (함수 사용)
• 뽑은 7명 중 ‘이다솜파’가 4명 이상인지 확인한다.
• 7명의 위치가 모두 연결되어 있는지 확인한다.

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

# 7명이 인접해 있는지 확인    
def bfs(x, y):
    # 인접한 사람 수 저장
    total = 1
    deq = deque()
    deq.append((x, y))
    # 방문 위치 제거
    visited[i][j] = 0

    while deq:
        x, y = deq.popleft()

        for k in range(4):
            ni = x + di[k]
            nj = y + dj[k]
            if 0 <= ni < 5 and 0 <= nj < 5 and visited[ni][nj] == 1:
                # 방문한 위치 제거
                visited[ni][nj] = 0
                deq.append((ni,nj))
                total += 1
    # 7명이 모두 인접해 있으면
    if total == 7:
        return 1
    return 0


students = [input() for _ in range(5)]
di = [0,1,0,-1]
dj = [1,0,-1,0]
cnt = 0

# 전체에서 7명 뽑는 경우를 combinations 함수 사용
for members in combinations(range(25), 7):
    # 7공주 체크
    visited = [[0] * 5 for _ in range(5)]
    # 임도연파 수 저장
    yCnt = 0
    
    for num in members:
        # 숫자를 활용하여 좌표로 표현한다.
        # 25번 까지 중 해당 번호의 행은 번호를 5로 나눈 몫
        i = num // 5
        # 25번 까지 중 해당 번호의 열은 번호를 5로 나눈 나머지
        j = num % 5
        # 위치 체크
        visited[i][j] = 1
        
        # 임도연파 카운트
        if students[i][j] == 'Y':
            yCnt += 1
        # 임도연파가 4이상이면 해당 경우는 탐색 안함
        if yCnt >= 4:
            break

    # 임도연파가 4미만(이다솜파 4이상)이고 7명이 연결되어 있으면
    if yCnt < 4 and bfs(i, j):
        cnt += 1

print(cnt)