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

1941번: 소문난 칠공주

from itertools import combinations
from collections import deque

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

area = [list(input()) for _ in range(5)]

positions = []

for i in range(5):
    for j in range(5):
        positions.append((i,j))

combs = list(combinations(positions,7))

answer = 0

def checkValid(givenComb): # 주어진 7개의 조합이 4개 이상의 다솜파 학생이 존재하는지 판단하는 함수
    s_count = 0
    for x,y in givenComb:
        if area[x][y] == "S":
            s_count += 1
    if s_count >= 4:
        return True
    else:
        return False

def checkAdjacent(givenComb): # 주어진 7개의 조합이 인접해 있는지 판단하는 함수
    visited = [False]*7

    q = deque([givenComb[0]])
    
    visited[0] = True

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if (nx,ny) in givenComb:
                next_index = givenComb.index((nx,ny))
                if not visited[next_index]:
                    q.append((nx,ny))
                    visited[next_index] = True
    if False in visited:
        return False
    else:
        return True
    
for comb in combs:
    if checkValid(comb):
        if checkAdjacent(comb):
            answer += 1

print(answer)

 

이번 문제는 주어진 5x5 영역에서 7개의 인접한 영역 중 'S'의 개수가 4개 이상인 경우의 수를 구하는 문제이다.

 

처음에 문제를 접근할 때는 DFS로 풀려고 했었는데, DFS 특성상 십자 모양으로 갈라지는 탐색을 하기는 어렵기 때문에 다른 방식으로 풀이해야 한다.

 

다른 분의 풀이를 참고해본 결과, DFS로 경로를 탐색하는 것이 아니라 combinations 라이브러리로 5x5 좌표 중 7개를 선택하는 경우의 수를 먼저 구해서 풀어야 한다.

 

먼저 combinations 로 가능한 위치 7개 조합을 뽑은 뒤, 'S' 가 4개이고(checkValid), 원소가 서로 인접해 있는지(checkAdjacent) BFS로 체크해서 풀었다.

 

느낀 점 및 배운 점

1. DFS/BFS 탐색으로는 십사 모양으로 갈라지는 탐색은 할 수 없다.
2. 십자 모양으로 갈라지는 탐색은 먼저 모든 경우의 수를 조합(combinations)으로 구하고, BFS로 연결되어있는지 확인해야 한다.
3. 1차원 리스트나 튜플에서의 방문 여부를 체크하기 위해서는 index를 사용해야 한다.
4. index() 함수는 리스트나 튜플 내 지정한 값이 몇 번째 인덱스에 속하는지를 알려주는 함수이다.