본문 바로가기
알고리즘/[python] 백준 BOJ

[python] 백준 1941 소문난 칠공주

by Alan_Kim 2023. 4. 18.
728x90
반응형

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

 

1941번: 소문난 칠공주

총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작

www.acmicpc.net

 

문제해결

  • 조건이 4가지를 만족해야하므로 차례대로 만족시킬 수 있는 방법이 뭔지 생각해본다.
  • 1번과2번조건을 묶고 3번과 4번 조건을 묶으면 좋다.
  • 7명의 여학생으로 구성되어있어야하므로 depth=7인 dfs를 사용하면 좋을 것 같다. (게다가 가로 또는 세로로 인접해 있어야하므로 dfs로 이동하는 것은 좋다.)
  • 임도연파가 4명 이상이면 안되는 것이기 때문에 중간에 그만두고 다른 것을 찾도록 한다.
  • bfs를 통해 가로 또는 세로로 이동해서 모두 연결할 수 있는지 확인한다.
  • 가능하면 정답변수 result +1 을 해준다.

 

CODE

from collections import deque

def bfs(arr):
    dr = [-1,+1,0,0]
    dc = [0,0,-1,+1]
    visited = [[1]*5 for _ in range(5)]
    for i in A:
        visited[i[0]][i[1]] = 0
    queue = deque([A[0]])
    visited[A[0][0]][A[0][1]] = 1
    check = 1
    while queue:
        r, c = queue.popleft()
        for ur, uc in zip(dr,dc):
            nr = r + ur
            nc = c + uc
            if 0<=nr<5 and 0<=nc<5:
                if not visited[nr][nc]:
                    visited[nr][nc] = 1
                    check += 1
                    queue.append((nr,nc))
    if check != 7:
        return False
    else:
        return True
def dfs(depth, start, count):
    global result
    if count >= 4: # 임도연파가 4명보다 많으면 중간에 early stopping
        return
    if depth ==7:
        if bfs(A):
            result += 1
        return
    for i in range(start, 25):
        r = i//5
        c = i%5
        A.append((r,c))
        dfs(depth+1, i+1, count+(seats[r][c] =='Y')) # 임도연파면 count+1 이다솜파면 count
        A.pop()


if __name__=='__main__':
    seats = [[str(c) for c in input().rstrip()] for _ in range(5)]
    A = []
    result = 0
    dfs(0,0,0)
    print(result)
728x90
반응형

댓글