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

최적화가 필요한 완전 탐색 문제

BFS로 풀기에는 복잡한거 같아서 DFS로 풀었다.

단순히 상하좌우 탐색으로 한붓그리기가 아니라
어찌됐든 가로세로 연결만 하면 되는 형태이기 때문에
일반적인 상하좌우 탐색 문제풀이에 익숙한 사람이라면 생각이 필요했을 것이다.

 

DFS로 풀기 위해선, 각 함수마다 3개의 정보가 필요하다고 생각했다.

1. 전체 탐색 횟수
2. Y를 만난 횟수
3. 지나온 경로

1번은 기저 조건을 만들기 위해 필요했고,
2번은 Y는 최대 3개까지 허용되니, 여기에 대한 기록이 필요했다.
3번같은 경우, 모든 탐색마다 기존에 지나온 경로에서 다시 상하좌우로 탐색이 필요했다.

당연한 거지만, 첫 탐색 지점이 Y인 것은 의미가 없다 생각해, S일 때 탐색을 시작했다.

최적화

나는 지나온 경로를 튜플 형태로 관리했기 때문에, 튜플 비교를 자주 수행했다.
그래서 모든 데이터가 S인 경우 시간 초과가 발생해, 최적화를 시도했다.

배열 차원 낮춤

가장 기초적인 방법으로 2차원 배열 탐색을 1차원 배열처럼 하는 방법이다.

중복 탐색 제거

처음 시작점이 된 S는 이후 탐색에서 배제된다.
왜냐하면, 해당 S가 들어가 있는 모든 경로는 이미 S를 시작점으로 했을 때 모두 만들어졌기 때문이다.

Map으로 중복 경로 검사

모든 데이터가 S인 경우, 선형 탐색이 생각보다 좋은 효율을 보이지 못했다.
따라서, 경로들을 오름차순 정렬해, map 형태로 관리했다.
쉽게 말하면, 트리 구조로 관리를 했다.

이 부분을 적용하니 중복 탐색에 대한 병목이 많이 줄었다.

 

코드

from collections import defaultdict

board = []
visit = {}
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
used = [[False for _ in range(5)] for _ in range(5)]
ans = 0

def main():
    for _ in range(5):
        board.append(input())
    for i in range(5):
        for j in range(5):
            if board[i][j] == 'S':
                dfs(1, 0, [i * 5 + j])
                used[i][j] = True
    print(ans)


def dfs(count, Y, route):
    if count == 7 and Y <= 3:
        global ans
        sortedRoute = sorted(route)
        current = visit
        same = 0
        for r in sortedRoute:
            if r not in current:
                current[r] = {}
            else:
                same += 1
            current = current[r]
        if same < 7:
            ans += 1
        return

    for r in route:
        hereY, hereX = r // 5, r % 5
        for d in dir:
            thereY, thereX = hereY + d[0], hereX + d[1]
            if thereY < 0 or thereY >= 5 or thereX < 0 or thereX >= 5:
                continue
            if used[thereY][thereX]:
                continue
            temp = thereY * 5 + thereX
            if temp in route:
                continue
            if board[thereY][thereX] == 'Y':
                if Y < 3:
                    dfs(count + 1, Y + 1, route + [temp])
            else:
                dfs(count + 1, Y, route + [temp])


if __name__ == "__main__":
    main()