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

Try1. 열심히 시도해봤고, 왜 틀렸는지 알 수 없는 알고리즘

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
answer = 0

def dfs(x, y, depth, count, path):
    global answer
    Visit[x][y] = True
    if depth-count > 3: 
        print(depth, count, path)
        return -1
    if depth == 7:
        if count >= 4: answer += 1
        print(path, answer)
        return -1

    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0 <= nx < 5 and 0 <= ny < 5 and not Visit[nx][ny]:
            if Grid[nx][ny] == "S": dfs(nx, ny, depth+1, count+1, path+"S")
            else: dfs(nx, ny, depth+1, count, path+"Y")


if __name__ == "__main__":
    # Grid = [list(input()) for _ in range(5)]
    Grid = [['Y', 'Y', 'Y', 'Y', 'Y'], ['S', 'Y', 'S', 'Y', 'S'], ['Y', 'Y', 'Y', 'Y', 'Y'],
    ['Y', 'S', 'Y', 'Y', 'S'], ['Y', 'Y', 'Y', 'Y', 'Y']]
    S_list = []
    for i in range(5):
        for j in range(5):
            if Grid[i][j] == "S":
                S_list.append((i, j))
    for coordinate in S_list:
        Visit = [[False for _ in range(5)] for _ in range(5)]
        sx, sy = coordinate
        dfs(sx, sy, 1, 1, "S")

일단, 모든 S파 학생들을 좌표에 넣어두고 해당 학생들로부터 시작하는 dfs 패스를 돌린다.
(탐색 수를 조금이라도 줄이고자 이렇게 했다)
그리고 중간에 S파 학생 수가 미치지 못하면 가지치기를 해줬다.

테스트 케이스는 맞게 돌아가는데 막상 제출했더니 틀렸다고 나온 코드다.

Try2. 정답 코드

from itertools import combinations
from collections import deque
import sys
graph = []
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
positions = [(i, j) for i in range(5) for j in range(5)]
combs = list(combinations(positions, 7)) # 25명 학생 중 7명을 임의로 뽑음
answer = 0

for _ in range(5):
    graph.append(list(sys.stdin.readline().strip()))


def checkDaSom(givenComb):
    # 이다솜(S)이 몇 명인지 셈
    daSom = 0
    for x, y in givenComb: # 7명 좌표중 임다솜 있을 때
        if graph[x][y] == 'S':
            daSom += 1
    return True if daSom >= 4 else False # 임다솜 파가 4명 이상이면 True


def checkAdjacent(givenComb):
    # itertools로 뽑은 7명이 인접해있는지 체크하는 bfs
    visit = [False]*7 # 7명 학생을 갈 수 있는지 확인
    q = deque()
    q.append(givenComb[0])
    visit[0] = True

    while q:
        x, y = q.popleft()
        for d in direction:
            nx = x + d[0]
            ny = y + d[1]
            if (nx, ny) in givenComb:
                nextIdx = givenComb.index((nx, ny))
                if not visit[nextIdx]:
                    q.append((nx, ny))
                    visit[nextIdx] = True
    # q를 전부 순회했는데도 여전히 방문하지 못한 학생이 있다면 인접한 것 X
    return False if False in visit else True


for comb in combs:
    if checkDaSom(comb):
        if checkAdjacent(comb):
            answer += 1

print(answer)

정답 코드 알고리즘은 굉장히 심플하다.
1. itertools를 이용해 25명중 임의의 7명을 뽑는다. (좌표 어레이가 나오게 된다)
2. 해당 7명 학생들이 인접해있는지 bfs로 체크한다.
3. 인접해있으면 case +=1

대다수 사람들이 이렇게 조합으로 풀었는데, 이 이유는 일렬로 늘어선 path를 찾는게 아닌, T자형이나 십자가형처럼 중간에 교차로가 있는 경우 dfs로 풀 수 없기 때문이다. 라고 한다.
하지만 내 생각엔 백트래킹으로 가능한 조합 아닌가? 싶기도 하다.