[백준 1941] 소문난 칠공주

문제

총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.

위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.

1. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
2. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
3. 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
4. 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.

여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.

 

출력

첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.

---

접근

문제에서 주어진 조건대로 칠공주를 구성했을 때 구성한 순서대로 다르게 판단하여 경우의 수를 증가시킬 수 있기 때문에 칠공주를 구성한 번호들을 기록하여 오름차순으로 정렬하여 기존에 구성한 적이 있는지 판단하였다.

그렇기 때문에 5x5 크기의 맵에서 각 칸을 순서대로 번호를 매겼고 선택할 때마다 해당 번호를 기록하였다.

 

또한 dfs 탐색을 진행할 때 십자가 모양은 탐색이 안되기 때문에 지금까지 기록한 번호를 토대로 상하좌우를 탐색하였다.

 

구현

- dfs에 지금까지 선택한 번호를 기록한 리스트와 이다솜파와 임도연파가 지금까지 몇 명으로 구성되어있는지 S, Y를 인자로 넘겨준다.

- 이때 Y가 3을 초과하면 안되고 넘게되면 바로 return한다.

- 지금까지 선택한 리스트의 길이가 7이고 S가 4이상일 때 알맞게 칠공주를 구성했는지 검사한다.

- 지금까지 기록한 것을 정렬하고 튜플형태로 변환 한것을 visited에 있는지 판단하여 없다면 경우의 수를 증가시킨다.

- 칠공주를 구성하기 위해서는

- 지금까지 기록한 번호들을 하나씩 꺼내어 해당 번호에 대한 상하좌우 탐색을 진행한다.

def dfs(picked, S, Y):
    global answer, visited
    if Y > 3:
        return

    if len(picked) == 7 and S >= 4:
        picked = tuple(sorted(picked))
        if picked not in visited:
            visited.add(picked)
            answer += 1
        return
    for pos in picked:
        y = pos//5
        x = pos%5
        dy = [1, -1, 0, 0]
        dx = [0, 0, 1, -1]
        for d in range(4):
            ny = y + dy[d]
            nx = x + dx[d]
            n = ny * 5 + nx
            if check_range(ny, nx) and n not in picked:
                picked.append(n)
                if graph[ny][nx] == 'Y':
                    dfs(picked, S, Y+1)
                else:
                    dfs(picked, S+1, Y)
                picked.pop()

---

전체 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

def check_range(y, x):
    return (0 <= y < 5) and (0 <= x < 5)

def dfs(picked, S, Y):
    global answer, visited
    if Y > 3:
        return

    if len(picked) == 7 and S >= 4:
        picked = tuple(sorted(picked))
        if picked not in visited:
            visited.add(picked)
            answer += 1
        return
    for pos in picked:
        y = pos//5
        x = pos%5
        dy = [1, -1, 0, 0]
        dx = [0, 0, 1, -1]
        for d in range(4):
            ny = y + dy[d]
            nx = x + dx[d]
            n = ny * 5 + nx
            if check_range(ny, nx) and n not in picked:
                picked.append(n)
                if graph[ny][nx] == 'Y':
                    dfs(picked, S, Y+1)
                else:
                    dfs(picked, S+1, Y)
                picked.pop()



graph = [input().strip() for _ in range(5)]
answer = 0
visited = set()
for i in range(5):
    for j in range(5):
        if graph[i][j] == 'S':
            picked = []
            picked.append(i * 5 + j)
            dfs(picked, 1, 0)


print(answer)