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

골드 Ⅲ

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

1941번: 소문난 칠공주

 

📄 문제

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

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

 

---

💡 아이디어

• 인접하고 ‘이다솜파’ 학생이 4명 이상 포함되는 모든 조건을 만족하는 7명을 그래프 탐색으로 바로 뽑는다.
• 5×5의 격자에서 깊이 우선 탐색(DFS)을 활용하여 4방향 탐색으로 인접한 7명을 뽑는다.
• ‘이다솜파’ 학생이 4명 이상 포함되어야 하므로 '이다솜파’ 학생의 위치를 찾아 깊이 우선 탐색(DFS)을 시행한다.
  • ‘이다솜파’ 학생이 무조건 포함되어 있어야 하므로 ‘임도연파’ 학생으로만 이루어진 경우를 미리 제외할 수 있다.
  • 따라서, 모든 점을 시작점으로 탐색하는 것보다 시간을 단축할 수 있다.

• 깊이 우선 탐색(DFS)을 통해 7명을 뽑는데 깊이 1 ~ 7까지의 뽑은 학생을 저장할 후보자 빈 배열(candidate)이 필요하다.
• 후보로 저장한 학생들(candidate) 의 각자 위치에서 4방향으로 인접한 다른 학생을 탐색한다.
• 인접한 학생을 한 명씩 뽑을 때마다
  • 해당 학생을 후보자 배열(candidate)에 저장한다. (append)
  • 인접한 학생이 ‘임도연파’ 학생인지 체크한다. (students[ni][nj] == 'Y')
  • 깊이 우선 탐색(DFS)의 재귀를 들어간다. (dfs(newY))
• ‘임도연파’ 학생이 4명 이상 포함되어 있는지 확인한다. (yCnt)
• ‘임도연파’ 학생이 4명 이상 포함되면 ‘이다솜파’ 학생이 4명 이상 포함될 수 없으므로 해당 경우의 탐색을 종료한다.
  • ‘이다솜파’의 학생이 적어도 4명 이상 포함 되어야 한다.
  • ‘임도연파’ 학생이 4명 이상 포함되면 해당 재귀를 탈출한다. (return)

• 재귀를 탈출하여 해당 경우의 탐색을 종료하면 이전 단계로 돌아와 추가한 후보자를 삭제한다. (pop)
• 이전 단계에서 돌아오면 이어서 현재 깊이(재귀)에 저장되어 있는 인접한 다른 후보자의 경우를 탐색한다. (candidate)
• 모든 조건을 만족하는 칠공주가 만들어지면 해당 후보자의 경우(candidate)를 정렬하여 튜플의 형태로 칠공주 집합(members)에 저장한다.
• 탐색이 종료된 재귀의 후보자 배열(candidate)은 다른 ‘이다솜파’ 학생의 위치를 시작점으로 새롭게  탐색을 시작할 때 중복 탐색을 방지하기 위해 저장한다. (visited)
• 따라서, 탐색이 끝난 후보자들의 방문 체크를 통해 시간을 단축시킨다.
• 모든 ‘이다솜파’ 학생을 시작점으로 하는 깊이 우선 탐색(DFS)이 끝나면 저장된 7명의 후보자들의 개수를 출력한다. (len(members))

 

---

다른 풀이 방법이 존재한다.

7명의 후보자들의 경우를 모두 뽑아 놓고 모든 조건을 만족하는 경우를 찾아 숫자를 세는 방법도 있다.

• ‘이다솜파’ 학생이 4명 이상 포함되어야 한다.
• 뽑힌 7명의 위치가 서로 인접한다.

 

https://bu119.tistory.com/67

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

 

📝 문제 풀이 (Code)

최종 코드 ( 실행시간 80 ms, 메모리 32276 KB, Python 3 )

후보자들의 방문 체크를 통해 시간을 단축시켰다.

• 재귀 탐색이 종료되면 후보자들의 경우를 저장한다.
• 다음 깊이 우선 탐색을 시행할 때, 탐색을 마친 중복된 후보자들인지 방문 체크한다.

import sys
input = sys.stdin.readline

def dfs(yCnt):
    global candidate

    # 임도‘연’파 학생수 체크
    if yCnt >= 4:
        return

    # 조건에 만족하는 칠공주 모이면
    if len(candidate) == 7:
        members.add(tuple(sorted(candidate)))
        return

    # 이미 확인한 후보 경우이면 리턴
    if tuple(sorted(candidate)) in visited:
        return

    # 각 위치에서 4방향 탐색으로 인접한 모든 경우 찾기
    for x, y in candidate:
        for k in range(4):
            ni = x + di[k]
            nj = y + dj[k]
            if 0 <= ni < 5 and 0 <= nj < 5 and (ni, nj) not in candidate:
                # 임도‘연’파 변화 저장
                newY = yCnt
                if students[ni][nj] == 'Y':
                    newY += 1
                candidate.append((ni,nj))
                dfs(newY)
                candidate.pop()

    # 확인이 끝난 후보들 방문 체크
    # 탐색이 끝나서 return되는 후보들
    visited.add(tuple(sorted(candidate)))


students = [input() for _ in range(5)]
di = [0,1,0,-1]
dj = [1,0,-1,0]
# 7공주 가능한 경우 저장
members = set()
# 멤버 후보 방문 체크
visited = set()

for i in range(5):
    for j in range(5):
        # 이다‘솜’파 이면 탐색
        if students[i][j] == 'S':
            # 멤버 선택
            candidate = [(i, j)]
            dfs(0)

# ‘소문난 칠공주’ 모든 경우의 수
print(len(members))

 

처음 코드 ( 실행시간 2504 ms, 메모리 31256  KB, Python 3 )

후보자들의 방문 체크를 하지 않는다.

• 5×5 행렬을 탐색하면서 ‘이다솜파’를 4명 이상 포함하고 인접해 있는 7명을 바로 뽑는다.
• 탐색이 종료된 재귀의 후보자들을 저장하지 않는다.

import sys
input = sys.stdin.readline

def dfs(yCnt):
    global candidate

    # 임도‘연’파 학생수 체크
    if yCnt >= 4:
        return
    # 조건에 만족하는 칠공주 모이면
    if len(candidate) == 7:
        members.add(tuple(sorted(candidate)))
        return

    # 각 위치에서 4방향 탐색으로 인접한 모든 경우 찾기
    for x, y in candidate:
        for k in range(4):
            ni = x + di[k]
            nj = y + dj[k]
            if 0 <= ni < 5 and 0 <= nj < 5 and (ni, nj) not in candidate:
                # 임도‘연’파 변화 저장
                newY = yCnt
                if students[ni][nj] == 'Y':
                    newY += 1
                candidate.append((ni,nj))
                dfs(newY)
                candidate.pop()


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

for i in range(5):
    for j in range(5):
        # 이다‘솜’파 이면 탐색
        if students[i][j] == 'S':
            # 멤버 선택
            candidate = [(i, j)]
            dfs(0)
            
# ‘소문난 칠공주’ 모든 경우의 수
print(len(members))