[백준][조합][BFS] 1941. 소문난 칠공주

1941. 소문난 칠공주

 

• 승규 풀이
  • skt 1번문제 처럼 2차원 배열 각 칸에 번호를 매겨놓고
  • 0~24번 칸 중 7개를 뽑는 조합을 생성한다
  • 조합이 된 번호들의 위치만 1로 바꿔두고 나머지는 0으로 채워둔 후
  • 값이 1인 값만 확인
    • 전체 값이 7이하 -> 이어져있지 않고 떨어진 사람이 있다! -> 실패
    • 전체 값 7
      • 이다솜 팸이 4이상이어야 -> 성공

from itertools import combinations
from collections import deque

graph = [list(input().rstrip()) for _ in range(5)]
number = [[0 for _ in range(5)] for _ in range(5)]

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

result = 0


def bfs(i, j):
    global result
    queue = deque()
    visited = [[False for _ in range(5)] for _ in range(5)]
    cnt = 0
    total = 1

    queue.append((i, j))
    visited[i][j] = True
    if graph[i][j] == 'S':
        cnt += 1

    while queue:
        x, y = queue.popleft()

        for k in range(4):
            nx = x+dx[k]
            ny = y+dy[k]

            if nx < 0 or nx >= 5 or ny < 0 or ny >= 5:
                continue
            if visited[nx][ny] == True:
                continue
            if number[nx][ny] == 0:
                continue

            total += 1
            visited[nx][ny] = True
            if graph[nx][ny] == 'S':
                cnt += 1
            queue.append((nx, ny))

    if total == 7:
        if cnt >= 4:
            result += 1


# 0~24까지 번호를 매김
for comb in combinations(range(25), 7):
    for c in comb:
        number[c//5][c % 5] = 1

    bfs(comb[0]//5, comb[0] % 5)

    # 다음 조합을 위해 0으로 초기화
    for c in comb:
        number[c//5][c % 5] = 0


print(result)