[Python / BOJ 1941] 소문난 칠공주

 

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

1941번: 소문난 칠공주

 

 

 

0. 문제

5x5 형태로 S(이다솜파) Y(이도연파) 값이 input이 주어진다.

격자에서 7명을 뽑되, 다음 조건을 만족시키는 경우의 수 개수를 구하라.

• 7명을 뽑고 이들은 모두 인접해있어야 한다.
• S는 4명 이상 뽑아야 한다.

 

 

 

 

1. 아이디어

현재 위치에서 하나씩 요소를 추가해나가면 되기 때문에 DFS / BFS 를 생각하기 쉽다.

예제의 답 (왼쪽은 괜찮지만 오른쪽이 문제)

하지만 베이직한 DFS / BFS 는 마지막 위치에서 4방향 중 한 쪽으로만 전파하기 때문에 위와 같이 Y에서 양쪽을 선택해야 하는 경우를 선택할 수 없다. 이를 해결하기 위해서, 지금까지 선택했던 경로에서 4방향으로의 전파를 모두 확인해야 한다.

이 때, 방문체크는 선택한 루트를 기준으로 해줘야한다.

예를 들어 [(0, 0), (1, 0)] 를 순서대로 선택한 경우와 [(1, 0), (0, 0)] 를 순서대로 선택한 경우 결과는 동일하다. 그래서 루트가 동일하면 더 이상 재귀하지 않도록 return 을 해야한다. 나는 set을 이용하여 이미 저장된 경로를 확인했다.

 

 

 

 

2. 구현

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def func(route, Y_member):
    global result

    # 가지 치기 => 임도연 파가 4명 이상되면 X
    if Y_member >= 4:
        return

    # route를 저장해두고, 이미 방문한 경우면 return
    tuple_route = tuple(sorted(route))
    if tuple_route in route_check:
        return
    else:
        route_check.add(tuple_route)

    # 종료 => 7명을 모두 픽했으면 종료
    if len(route) == 7:
        result += 1
        return

    # 재귀 => 모든 route 포인트에서 4방향으로 전파할 수 있다
    for r, c in route:
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            # 범위 바깥이거나 이미 방문한 곳
            if not (0 <= nr < 5 and 0 <= nc < 5) or ((nr, nc) in route):
                continue
            # 갈 수 있는 곳
            if IN[nr][nc] == 'Y':
                func(route + [(nr, nc)], Y_member + 1)
            else:
                func(route + [(nr, nc)], Y_member)


IN = [list(input()) for _ in range(5)]
result = 0
route_check = set()

for r in range(5):
    for c in range(5):
        Y_member = 1 if IN[r][c] == 'Y' else 0
        func([(r, c)], Y_member)

print(result)