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

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

# 소문난 칠공주

from collections import defaultdict
import sys
input = sys.stdin.readline
arr = []
for _ in range(5):
    arr.append(list(input().strip()))
visited = defaultdict(bool)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def back_tracking(people):
    global result
    # (해당 people의 숫자를 arr좌표상의 문자열로 바꿔서 문자열로 join)의 'Y'의 개수
    if (''.join([arr[i//5][i % 5] for i in people]).count('Y')) > 3:
        return
    # 7명이라면
    if len(people) == 7:
        # people을 정렬
        temp = sorted(people)
        # 문자열로 바꾸고
        temp_str = ''.join(list(map(str, temp)))
        # 딕셔너리에 없으면 result += 1
        if temp_str not in visited:
            visited[temp_str] = True
            result += 1
        return
    for person in people:
        # 0번부터 24번인 person을 좌표로 바꿔줌
        x = person // 5
        y = person % 5
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < 5 and 0 <= ny < 5:
                # 좌표를 다시 0번부터 24번으로 바꿔줌
                person_num = nx*5+ny
                if person_num not in people:
                    people.append(person_num)
                    back_tracking(people)
                    people.pop()


result = 0
for i in range(25):
    back_tracking([i])
print(result)

 

백트랙킹
1. arr을 입력을 받고, visited를 defaultdict(bool)로 선언
2. 2차원 배열을 1차원으로 변환해서 모든 좌표마다 back_tracking실시 (people초기값 각 좌표의 시작 값)
    - 현재까지 고른 사람들 중 'Y'가 3 초과 라면 return
    - 그 외 7명을 모두 골랐다면 : people리스트를 정렬하고 딕셔너리화해서 중복 값 관리, 중복이 안된다면 : result 출력
    - 7명이 되기 까지, 각 좌표의 상하좌우를 탐색하고 back_tracking을 이용하여 people에 append 해나간다.
3. result 출력

 

새로운 유형의 백트랙킹이다.

중복 값 관리를 어떻게 해야 할지 막막하던 찰나 2차원 상의 좌표를 1차원 좌표로 바꿔주고 정렬하여 문자열로 관리를 했다.

도중에 'Y'의 값이 4 이상이 되면 return 해주어 시간 복잡도를 신경을 써줬다.

 

사실 people로 관리하지 않고 back_tracking 인자에 Y의 개수, S의 개수를 이용해서 관리하면

분기별로 return 해줄 때, 리스트로 바꾸고 count를 하는 등의 불필요한 시간 복잡도가 필요하지 않다.

해당 코드는 충분히 최적화가 가능하다.