[백준 #1941, Python] 소문난 칠공주 👸

헤헷^^,,백만년만의 블로그,,포스팅,,그리구 백만년만의 알고리즘,, 지난주는 뭐,,인적성하니라 어쩌구,, 이번주는 몸상태랑 멘탈이 박살나서 어쩌구^^,, 무튼 핑계로 가득차서 나태했던 나의 블로그,,4월이 마지막 포스팅 실화냐,,? ㅋㅅㅋ,,이제 방학이 곧이니까 열심히 해봐야지,,,아자아자 화이팅.. sk인적성에서 힘든일이있은후에 회복이 빠르다 문항 아니다라고 체크하길 잘했다 ^~^,,인성에서 적발될뻔햇자누!

[문제]

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

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

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

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

[코드]

 

from sys import stdin

def permu(idx,ans,position):
    global cnt,check

    if ans.count('Y') > 3:
        return
    if idx == 7:
        if ans.count('S') >= 4:
            position_check(position[0],position)
            if sum(sum(check,[])) == 7:
                cnt += 1
            check = [[0] * 5 for _ in range(5)]
        return
    for i in range(25):
        if visit[i] == 0:
            visit[i] = 1
            permu(idx+1,ans+arr[i],position +[i])
            for j in range(i+1,25):
                visit[j] = 0

def position_check(s,position):
    r = s // 5
    c = s % 5
    check[r][c] = 1
    for j in range(4):
        nr = r + dr[j]
        nc = c + dc[j]
        if 0<=nr<5 and 0<=nc<5:
            next = nr*5 + nc
            if check[nr][nc] == 0 and next in position:
                check[nr][nc] = 1
                position_check(next,position)


arr = []
cnt = 0
for _ in range(5):
    arr += list(map(str,stdin.readline().strip()))
visit = [0 for _ in range(25)]
check=[[0]*5 for _ in range(5)]
dr =[-1,1,0,0]
dc = [0,0,-1,1]
permu(0,'',[])
print(cnt)

 이 문제는 새롭게 배웠던게 많은 문제였다.. 그냥 bfs/dfs탐색으로는 7명 조합(조건 부합하는 : 다솜짱네가 4명이상인거..) 이런 조건을 만족하는 조합을 만들 수 가 없었다! 십자가 모양으로 이루어져있기 때문인듯,,

그래서 사람들의 코드를 참고해서 풀이한 방법은 다음과 같다.

1. 5*5의 이중 arr가 아닌, 일렬로 데이터를 받아와서 탐색한다. 일단 그냥 7명의 조합을 다 만들고, 거기서 나중에 붙어있는걸 확인하는 방식!

2. 붙어있는거를 어떻게 확인하지? 

그냥 1차원arr에서(정사각형) idx가 주어지면 그 idx를 행의 크기로 나눈 몫은 r이 되고, 나머지는 열의 값이 된다!

즉, r = idx // 5, c = idx % 5 이런식!

3. 위의 방식에 착안하여, 그냥 7명 조합에서 가장 첫번째 녀석을 dfs돌려주면 되고, 나중에 방문 check한 녀석이 7개가 되면, 그건 인접한 조건까지 만족한 녀석이니까, cnt를 올려준다.

✔ 또 여기서, 이중 list에서 한 요소의 합?을 알고싶을때 sum(sum(list,[])) 이렇게 하면 안에 sum(list.[])에서 한줄의 총 합들이 나오고, 그 다음에 그걸 다합쳐주는 식으로 해서 list의 총합을 구할 수 있다.. 왕 신기..

4. 이렇게 하고도 답이 나오지 않아서 ( 정확하게 말해서는 조건을 만족하는 7명 조합이 나오지 않음), 왜인가 했더니 내가 순열으로 만들어서 그랬다.. 그냥 조합으로 만들어주면 된다..뚱..땅,,