[백준] 1941번 : 소문난 칠공주

1941번: 소문난 칠공주

해당문제는 완전탐색과 백트래킹 문제로 특정한점 (i,j)로부터 7명의 학생수를 연속으로 방문한 경우의 수 중에서 조건에 만족하는 경우의 수만 카운팅 하면 된다.

1. 7명의 여학생들로 구성되어 있어야한다 DFS탐색을 하였을때 길이가 7인 경우
2. 7명은 가로나 세로로 반드시 인접해야함 DFS탐색을 할때 상,하,좌,우로 움직인다.
3. 화합과 번영을 위해 반드시 이다솜파 학생들로만 구성될 필요는 없다. (Y,S 혼용가능)
4. 반드시 이다솜파가 우위를 점하여야 한다. 이다솜파는 적어도 반드시 4명을 포함해야한다. ( 만약 임도연 파가 4명이 이상이 될경우 조건을 만족시키지 못함으로 탐색을 중지한다)

이 문제에서 중요한 포인트는 중복탐색을 방지해야한다. 예를들어 (0,0)에서 탐색한 결과와 (1,1)에서 탐색한 결과가 동일 할 수 있기때문에 2차원 배열의 방문 리스트를 1차원으로 변경한뒤 정렬을하여 딕셔너리 자료구조를 활용하여 방문처리를 해준다.

<aside> 💡 다국어로 문제를 해결하였습니다.

</aside>

from pprint import pprint
from collections import deque

moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
table = []
for _ in range(5):
    table.append(list(input()))

count = 0
visited = [[False for _ in range(5)] for _ in range(5)]  # 방문 표시
route = dict()
def dfs(jersey, holstein, people):
    global count
    if holstein >= 4:
        return

    if holstein + jersey >= 7:
        if jersey > holstein:
            temp = sorted(people, key=lambda c: (c[0] + c[1] * 5))
            key = ''
            for p in temp:
                key += str(p[0] + p[1]*5)
            if key not in route:
                #print(char, temp)
                count += 1
                route[key] = True
            return
        return

    for p in people:
        y = p[0]
        x = p[1]
        for dy, dx in moves:
            ny = dy + y
            nx = dx + x
            if 5 > ny >= 0 and 5 > nx >= 0 and not visited[ny][nx]:  # 배열범위에 들어있는 경우 탐색
                visited[ny][nx] = True
                people.append((ny, nx))
                if table[ny][nx] == 'S':
                    dfs(jersey + 1, holstein, people)
                else:
                    dfs(jersey, holstein + 1, people)
                visited[ny][nx] = False
                people.pop()

for i in range(5):
    for j in range(5):
        visited[i][j] = True
        people = []
        people.append((i, j))
        if table[i][j] == 'S':
            dfs(1, 0, people)
        else:
            dfs(0, 1, people)
        visited[i][j] = False

print(count)