[BOJ] 1941. 소문난 칠공주(Python) / DFS, Backtracking

1941번: 소문난 칠공주

전형적인 Backtracking 문제이다. 내가 매우 취약한 알고리즘.. 이번 주는 백트래킹/DFS 문제를 파보자

• 사용 알고리즘 : Backtracking / DFS 재귀로 조합 구현
• 조합으로 접근해야한다는 것을 생각도 하지 못했다. 가짓 수가 너무 많을 것이라 생각했는데,
• 백트래킹으로 Y를 4번 이상 만났다면 return하여 가지치기로 어느정도 거를 수 있다.
• dfs 함수로 25개 칸에서 7개 칸을 선택하는 조합을 구현한다.
  • 이 때, 7개 숫자를 리스트로 담는데, 0~24 숫자를 5*5맵의 좌표로 변환해주며 탐색한다. 
  • 해당 위치가 "Y"면, ycnt + 1하며 재귀로 넘겨주고, "S"라면 그냥 인자를 그대로 넘긴다.
  • 중요한 건 depth도 사용하지 않고, ycnt도 사용하지 않고 인덱스만 넘기는 경우가 있으므로 dfs(depth, ycnt, idx+1) 이 코드가 꼭! 필요하다.
  • ycnt가 3이 넘거나 탐색할 남은 숫자가 나의 남은 선택 수보다 작으면 가지치기를 해준다. 
  • 만약 depth가 7에 다다르면 7개 위치를 선택한 것이므로, 만들어진 숫자 조합인 p 리스트에 대해 ~
• check 함수를 통해 7개 좌표들이 서로 연결된 좌표인지 확인한다.
  • 마찬가지로 0~24로 구성된 숫자를 5*5맵에 맞는 좌표로 변환, 4방향 탐색을 통해 갈 수 있는 곳의 숫자가 현재 조합 숫자에 포함된 숫자라면 재검사를 위해 재귀 시전!
  • 전역 변수 visited 맵에 방문 표시, available 변수 += 1해준다.
  • 매 조합의 경우마다 visited과 available 변수를 초기화해줘야 한다!!!
  • 만약 available == 7이라면 7개의 위치 좌표가 서로 연결된 것이므로 답으로 출력할 result에 +1 해준다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)
        
def check(num):
    global available    
    r = num // 5
    c = num % 5
    for d in range(4):
        nr = r + dr[d]
        nc = c + dc[d]
        if not (0 <= nr < 5 and 0 <= nc < 5) or visited[nr][nc]:
            continue
        nextNum = nr*5+nc   # 다음 숫자
        if nextNum in p:    # p에 있다면 방문표시, 재귀로 다음 숫자 넘겨 재검사
            visited[nr][nc] = 1
            available += 1
            check(nextNum)

# (depth, Y의 갯수, 사용할 숫자 인덱스)
def dfs(depth, ycnt, idx):
    global result, available, visited
    if ycnt > 3 or 25-idx < 7-depth:    # 가지치기
        return

    if depth == 7:                  # depth가 7에 도달하면 연결 여부 검사
        available = 1               # 연결된 좌표 갯수
        visited = [[0] * 5 for _ in range(5)]
        sr, sc = p[0]//5, p[0]%5    # 5*5 맵 좌표로 변환
        visited[sr][sc] = 1         # 시작 위치 표시
        check(p[0])                 # 연결된 좌표인지 확인
        if available == 7:          # 7개 좌표가 연결됐다면 +1
            result += 1
        return

    # 5*5 맵 좌표로 변환
    r = idx // 5    
    c = idx % 5

    if A[r][c] == "Y":              # "Y"이면 ycnt +1
        p.append(idx)
        dfs(depth+1, ycnt+1, idx+1)
        p.pop()
    else:                           # "S"이면 그냥 넘기기 
        p.append(idx)
        dfs(depth+1, ycnt, idx+1)
        p.pop()
    dfs(depth, ycnt, idx+1)         # 꼭 필요한 코드. 사용하지 않고, 그냥 인덱스만 넘긴다!

# main
A = [input().rstrip() for _ in range(5)]
visited = [[0] * 5 for _ in range(5)]
result = 0
p = []
dfs(0, 0, 0)
print(result)

---

• 시간 : 528ms / 메모리 : 129124kb
• 고찰 : 까다로운 백트래킹 문제였다. 음.. 뭔가 발상이 좀 필요했다. 5*5맵의 각 위치별 인덱스를 부여하여 푸는 문제가 생각보다 많이 나오더라, 익숙해지자. 요새 너무 bfs에 치중되게 문제를 풀어 dfs, backtracking 알고리즘 문제풀이에 감이 좀 떨어진 것 같다. 혼자 힘으로 툭툭 잘 풀어내고 싶다!