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

Algorithm

1. '임도연파'는 4명이 넘지 않도록 총 7명의 학생들로 구성
2. 담은 학생들을 상대로 상하좌우 서로 인접한지 확인
   
   

def dfs(c, point, yc):
    global ans
    if yc >= 4:
        return
    if c == 7:
        if check():
            ans += 1
        return


    for cur in range(point, 25):
        x = cur // 5
        y = cur % 5

        Set.append(cur)
        if board[x][y] == 'Y':
            dfs(c + 1, cur + 1, yc + 1)
        else:
            dfs(c + 1, cur + 1, yc)
        Set.remove(cur)

       KEY POINT

• 2차원 배열의 1차원 배열 표기법
  x = point // 5, y = point % 5
  
  

• 그래프의 오름차순적 접근 (1, 2, 24 -> 1, 3, 4)
  각 재귀마다 현재 지점으로부터 for문 탐색

def check():
    queue = deque()
    queue.append(Set[0]) # start
    visited = [False for _ in range(25)]
    visited[Set[0]] = True

    count = 1
    while queue:
        index = queue.popleft()
        tx = index // 5
        ty = index % 5
        for k in range(4):
            nx, ny = tx + dx[k], ty + dy[k]
            Next = nx * 5 + ny
            if 0 <= nx < 5 and 0 <= ny < 5 and not visited[Next]:
                if Next in Set:
                    visited[Next] = True
                    count += 1
                    queue.append(Next)
    if count == 7:
        return True
    else:
        return False