[ 백준 ] 1941 소문난 칠공주 (python)

 

 

 

 

 

 

 

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

1941번: 소문난 칠공주

 

 

 

💡 접근 방법

7명의 여학생이 구성되어야 하는 경우의 수를 구하는 문제였기 때문에 백트래킹을 사용해서 문제를 풀어보려고 했다.

기본적인 백트래킹은 이 경우가 포함될 때, 포함되지 않을 때를 고려해서 재귀 함수로 확인을 해야하는데

여기에 상, 하, 좌, 우가 인접해있는 경우 인지도 함께 고려해야 해서 너무 어려웠다.

 

지금까지 풀어왔던 알고리즘 문제들을 생각하면, 인접해있는 좌표를 구할 땐 BFS를 사용해왔고

백트래킹같이 재귀 함수를 사용할 땐 DFS를 사용해왔기 때문에 어떻게 접근해야 하는지 한참 고민했다.

 

결론은 두 가지 방법 다 도전해봤는데 원하는 대로 풀리지 않았다..😥 백트래킹 너무 어려워....😥

N과 M문제 풀면서 이렇게 푸는 거구나! 했는데.. 응용문제 만나자마자 으엥?😲 상태 됐다

 

아무튼 오래 고민해도 정답을 찾지 못해서 다른 분의 풀이를 보고 문제를 풀어냈다.

 

 

 

 

 

 

🔥 문제 풀이 1

 

우선 5 * 5 배열을 활용해 문제를 푸는 것이 아닌, arr[25] 이렇게 1차원 배열로 두고 문제를 풀었다.

그리고 DFS를 활용해 재귀적으로 백트래킹하며 문제를 한 번에 풀어내는 것이 아니라,

DFS 함수를 통해 경우의 수를 구하는 것이었다. 그리고 그 경우의 수 중 상하좌우가 인접해있다면 조건에 만족한다고 판단하며 문제를 풀어내는 것이다.

 

그리고 시간 초과를 막기 위해서 가지치기도 진행해줘야 한다.

만약 현재 담겨있는 학생 중에 'Y' 임도연파가 더 많다면 가지치기

만약 현재 칠공주파에 담기지 않은 남은 학생의 수 < 칠공주파의 빈자리 일 경우 가지치기

 

또한 주의해야 할 점이 있다!

바로 visited 리스트를 경우의 수마다 갱신해줘야 한다는 것이다.

왜냐하면 하나의 경우의 수가 만들어졌을 때, visited를 사용해 인접한 거리에 있는지 확인하기 때문이다(check 함수)

 

 

말로 설명하면 좀 어렵기 때문에 아래 코드를 보고 이해해보자!

 

import sys
input = sys.stdin.readline
 
lst = [list(input().rstrip()) for _ in range(5)]
 
visited = [[0] * 5 for _ in range(5)]
res = 0
seven= []
 
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
 
def check(n):
    global visited
 
    # n -> 5*5 배열을 25칸짜리 1차원 배열로 나타냈을 때, 첫번째 칠공주의 위치
    x = n % 5
    y = n // 5
 
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
 
        if nx < 0 or nx >= 5 or ny < 0 or ny >= 5:
            continue
            
        if not visited[nx][ny]:
            # 좌표로 변경한 nx, ny를 다시 1차원 배열로 만드는 방법
            # (y좌표 * 5 + x좌표)
            if (ny * 5 + nx) in arr:
                visited[nx][ny] = 1
                check(ny * 5 + nx)
 
 
 
def dfs(cnt, idx, ycnt):
    global res, visited
 
    # 가지치기를 위해 'Y'가 4개 이상이거나,
    # 남은 사람의 명수가 필요로하는 갯수보다 적으면 가지치기!
    if ycnt >= 4 or 25 - idx < 7 - cnt:
        return
 
    # 7명이 모여졌다면, 인접한 자리끼리 모인건지 확인
    if cnt == 7:
        check(seven[0])
 
        if sum(sum(visited, [])) == 7:
            res += 1
 
        # 매 경우마다 visited를 새롭게 갱신해준다
        visited = [[0] * 5 for _ in range(5)]
        return
 
 
    # 5*5 행렬을 a[25]로(일자로) 구현하기 때문에
    # 좌표를 알기 위해서 진행하는 과정
    x = idx % 5
    y = idx // 5
 
    seven.append(idx)
    
    if lst[x][y] == 'Y':
        dfs(cnt + 1, idx + 1, ycnt + 1)
    else:
        dfs(cnt + 1, idx + 1, ycnt)
 
    # 이번 학생은 칠공주 멤버로 넣지 않는 경우
    # 다음 학생을 확인하기 위해 idx만 +1 해준다
    seven.pop()
    dfs(cnt, idx + 1, ycnt)
 
 
dfs(0, 0, 0)
print(res)
 
    
 
 
 

 

 

 

 

 

 

🔥 문제 풀이 2

 

이어서 백트래킹을 사용하지 않고, combinations를 사용해 풀어낸 풀이 방법이다.

 

combinations를 사용해 모든 경우의 수를 만들고, 경우를 따져서 인접한 거리에 있는지 & 이다솜 파 인 학생이 4명 이상인지 확인하고 조건에 맞다면 res +=1 해주는 방법으로 백트래킹을 사용하지 않아서 내 경우엔 이게 더 쉽게 느껴진다...🙄

 

그래도 다양한 풀이 방법을 알고 있어야 하기 때문에 만약 이 글을 읽고 있다면, 두 가지 방법 다 도전해보길 바란다!

 

from collections import deque
from itertools import combinations
import sys
input = sys.stdin.readline
 
lst = [list(input().rstrip()) for _ in range(5)]
arr = [(i, j) for i in range(5) for j in range(5)]
res = 0
 
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
 
def check_count(combi):
    count = 0
    for x, y in combi:
        if lst[x][y] == 'S':
            count += 1
 
    return True if count >= 4 else False
    
 
def check_pos(combi):
    visited = [False] * 7
    queue = deque()
    queue.append(combi[0])
 
    visited[0] = True
 
    while queue:
        x, y = queue.popleft()
 
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
 
            if (nx, ny) in combi:
                idx = combi.index((nx, ny))
                if not visited[idx]:
                    visited[idx] = True
                    queue.append((nx, ny))
 
    return False if False in visited else True
 
 
# combinations를 통해 좌표들의 조합 7개를 찾아낸다
for combi in combinations(arr, 7):
    # 좌표들의 위치에 'S' 이다솜파가 몇명인지 확인
    if check_count(combi):
        # 좌표들이 모두 인접해있는지 확인
        if check_pos(combi):
            res += 1
 
print(res)