[백준 알고리즘] 1941.소문난 칠공주 _ python

 

 

다른 사람들 풀이 방법 참고해가며 푼 문제...!!

 

 

처음에는 DFS로 돌리면 찾을 수 있을 것 같아 DFS로 짰지만, 십자배열 모양은 DFS 특성상 찾아지지 않아 실패했다. 

 

 

 

 

그래서 다른 분들의 접근방법을 참고해봤더니,

 

1) 5*5 배열의 각 자리수를 카운트해서 이를 인덱스를 활용함을 배웠다.

 

 

예를 들어,  왼쪽부터 0, 1, 2, 3, 4 .... 이라고 센다면 1,0은 5가 된다. 그리고 5를 5로 나누면 몫은 1, 나머지는 0 으로 5번째의 행과 열을 구할 수 있게 된다. 

 

새로운 접근 방법이라 생각하지 못했는데, 다른 문제 풀때도 활용할 수 있을 것 같으므로 기억해놓자.

 

 

 

2) 백트래킹할 때 주의하기

 

코드 논리나 다른 거는 다 맞은 것 같은데 계속 실패가 나왔다. 

 

크게 2가지로 코드를 나눴는데, 25개 중 7개를 뽑는 코드 + 뽑은 코드가 인접노드에 위치해있는지 였다.

 

정답 코드를구해서 같이 돌리면서 어떤 부분에서 답이 다른 지 보니, 마지막에 (4, 4)인 답들이 걸러지는 것을 알게 되었다. 

 

알고보니 백트래킹으로 사용했던 if cnt == 25: return 에서 문제가 발생했다.

 

cnt == 25 일때 는 5,0 이므로 걸러줘야 되는 것은 맞았으나, 함수의 맨 첫줄에 위치시켜 7개자리의 끝이 4, 4 인 경우도 걸러져 정답이 틀렸던 것이다..ㅠ

 

그래서 if cnt == 25: return  를 뽑고난 뒤 이후로 위치시켜 해결했다.

 

 

백트래킹 할때 걸러내는 코드의 위치가 중요하다는 말은 들어왔는데, 직접 경험한 것은 처음이었다... 이것 때문에 몇 시간을 헤맸는데... 덕분에 다음에는 헤매지 않을 것 같다.....ㅂㄷㅂㄷ

 

 

 

 

내 코드가 틀린지 알 수 있는 반례

 

SSSSS

SSSSS

SSSSS

SSSSS

SSSSS

=> 3546 

 

 

from collections import deque
delta = [(0, 1),(0, -1), (1, 0), (-1, 0)]
def make_crew(cnt, sel, S_cnt):
    global ans
    # X 자리밖에 안남았는데 X 합해도 S_cnt 4를 못넘을떄
    if S_cnt + (7 - sel) < 4 : return
    if sel == 7 :
        if S_cnt >= 4 and check_bfs():
            ans += 1
        return
    if cnt == 25: return
    r = cnt // 5
    c = cnt % 5
    select[sel] = (r, c)
    make_crew(cnt + 1, sel + 1, S_cnt + 1 if arr[r][c] == 'S' else S_cnt)
    make_crew(cnt + 1, sel, S_cnt)
    return


def check_bfs():
    visited = [[0]*5 for _ in range(5)]
    check = 1

    for i in range(1, 7):
        visited[select[i][0]][select[i][1]] = 1

    Q = deque()
    Q.append((select[0][0], select[0][1]))

    while Q:
        r, c = Q.popleft()
        for dt in range(4):
            nr = r + delta[dt][0]
            nc = c + delta[dt][1]
            if nr < 0 or nc < 0 or nr >= 5 or nc >= 5 :continue
            if visited[nr][nc]:
                check += 1
                visited[nr][nc] = 0
                Q.append((nr, nc))
                if check == 7:
                    return True
    return False

arr = [input() for _ in range(5)]
select = [-1] * 7
ans = 0
make_crew(0, 0, 0)
print(ans)