[BOJ, Python] 소문난 칠공주

1941번: 소문난 칠공주

풀이 

1. 먼저 25명(5X5) 중에 7명을 뽑는 경우를 구합니다. 조합(순서는 신경쓰지 않음) 으로 for문을 25만큼 돌면서 visited[i // 5][i % 5]를 방문체크해서 모든 조합을 구합니다. 

 

2. 구한 조합이, 서로 가로세로로 붙어있는지 체크하기 위해 bfs를 돌립니다. bfs로 4방 탐색을 하면서, 방문한 적 있으면 조합에 속하는 학생이라는 의미이므로 솜파이면 som +=1, 도연파이면 doyeon += 1을 진행합니다. 

 

3. bfs를 끝내고 솜파와 도연파의 합이 7이 아니라면, 7공주가 서로 붙어있지 않은 것이므로 false를 리턴합니다. 또한 솜파가 4 미만이면 솜파가 칠공주의 다수가 아니므로 조건을 만족하지 않아 false를 리턴합니다. 이 두가지 조건을 모두 만족한다면 true를 리턴합니다. 

 

코드에 주석을 달아두었으니 참고하시면 좋을 것 같습니다. 

정답 코드 

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(depth, start):  #25명의 학생 중, 7명의 조합을 구하는 함수 
    global ans
    if depth == 7:
        if bfs() : #이어져 있고, 솜파의 승리라면 ans +=1
            ans += 1
        return
    for i in range(start, 25):
        visited[i // 5][i % 5] = 1
        dfs(depth + 1, i + 1)
        visited[i // 5][i % 5] = 0

def bfs(): #이어져 있고, 솜파의 승리인지 체크
    som = 0; doyeon =0
    visited2 = [[0] * 5 for _ in range(5)]
    x = 0; y = 0
    for i in range(5):  #그래프를 복사하고, 큐의 시작점을 설정하기 위해 조합의 학생 하나를 저장
        for j in range(5):
            if visited[i][j]:
                visited2[i][j] = visited[i][j] 
                x = i;  y = j
    q = deque()
    q.append((x, y)) 
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= 5 or ny >= 5: continue
            if visited2[nx][ny]:  #방문한 적 있다면, 조합에 포함된 학생이므로 
                visited2[nx][ny] = 0  
                q.append((nx, ny))  #큐에 추가 
                if graph[nx][ny] == 'S': som +=1  #솜파이면 som 추가
                else: doyeon += 1  #도연파이면 doyeon 추가 
    if som + doyeon != 7: return False  #som + doyeon이 7이 아니라면, 가로세로로 붙어있지 않은 것이므로 return False
    elif som < 4: return False  #som이 4보다 작으면, 솜파가 7공주의 다수가 아니므로 return False
    else: return True

graph = [list(input()) for _ in range(5)]
visited = [[0]*5 for _ in range(5)]
ans = 0

dfs(0, 0)
print(ans)

엄청난 고민을 하게 한 문제입니다.. 아직 멀었네요 ㅠㅠ