[BOJ] 백준 1941번 문제 풀이 (Python)

1. 문제 풀이

조합과 BFS를 활용해서 문제를 해결하였습니다.

• $5\times5$ 칸마다 0 ~ 24까지 번호를 붙입니다.
• 조합을 활용해 0 ~ 24까지의 숫자 중 7개를 선택하는 모든 경우의 수를 탐색합니다.
• 선택된 7개의 수 중에서 이다솜파 4명의 위치가 포함되어있다면 BFS를 활용해 가로나 세로로 인접해있는지 확인합니다.

2. 코드

import sys
from collections import deque
from itertools import combinations,chain
def input(): return sys.stdin.readline().rstrip()

def check(case):
    my = [1,-1,0,0]
    mx = [0,0,1,-1]
    visited = set(case[1:])
    q = deque([case[0]])
    while q:
        y, x = q.popleft()
        for idx in range(4):
            dy, dx = y + my[idx], x + mx[idx]
            if dy < 0 or dx >= 5 or dx < 0 or dx >= 5: continue
            if (dy, dx) in visited:
                visited.remove((dy,dx))
                q.append((dy,dx))
    if visited:
        return False
    return True

matrix = [ list(input()) for _ in range(5)]
nums = [s for i, s in enumerate(chain(*matrix))]
location = {5 * i + j: (i, j) for i in range(5) for j in range(5)}

result = 0
for array in combinations(range(25), 7):
    count = sum(map(lambda x: 1 if nums[x] == 'S' else 0, array))
    if count >= 4 and check(list(map(lambda x: location[x], array))):
        result += 1
print(result)

itertools의 chain 함수는 다음과 같이 동작합니다.

# 출처: https://docs.python.org/ko/3/library/itertools.html#itertools.chain
def chain(*iterables):
    # chain('ABC', 'DEF') --> A B C D E F
    for it in iterables:
        for element in it:
            yield element