감시 피하기

💻 입력 조건

• 첫째 줄에 자연수 N이 주어집니다. (3 <= N <= 6)
• 둘째 줄에 N개의 줄에 걸쳐서 복도의 정보가 주어집니다. 각 행에서는 N개의 원소가 주어지며, 공백으로 구분합니다. 해당 위치에 학생이 있다면 S, 선생님이 있다면 T, 아무것도 존재하지 않는다면 X가 주어집니다. 단 항상 빈칸의 개수는 3개 이상으로 주어집니다.

💻 출력 조건

• 첫째 줄에 정확히 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지의 여부를 출력합니다. 모든 학생들을 감시로부터 피하도록 할 수 있다면 "YES", 그렇지 않다면 "NO"를 출력합니다.

💻 입력 예시1

5
X S X X T
T X S X X
X X X X X
X T X X X
X X T X X 

💻 출력 예시1

YES

💻 입력 예시2

4
S S S T
X X X X
X X X X 
T T T X 

💻 출력 예시2

NO

📖 문제 해결
dfs 알고리즘(solution 1.) 혹은 combinations 함수(solution 2.)를 이용하여 3개의 장애물을 설치하는 모든 경우의 수에 대해 고려할 수 있도록 하였고, moniter 이라는 함수를 구현하여 선생님께서 상하좌우 일직선 위에 있는 모든 위치를 다 확인할 수 있도록 하였습니다.

# solution 1. bfs를 이용한 풀이
# n 입력 받기
n = int(input())

# 복도 정보 입력 받기
map_ = []
for i in range(n):
    map_.append(list(map(str,input().split())))
    
# 복도 정보에서 선생님 좌표 찾기
T_coordis = []

for r_idx, row in enumerate(map_):
    for c_idx, col in enumerate(row):
        if map_[r_idx][c_idx] == 'T':
            T_coordis.append((r_idx, c_idx))

# moniter 함수 구현 : 선생님의 감시를 구현
def moniter(map_):

    result = 'Yes'

    for T_coordi in T_coordis:
        row_ = T_coordi[0]
        col_ = T_coordi[1]

        for i in range(1, n):

            # 열 아래 감시
            if row_ + i > n-1:
                break

            else:
                if map_[row_+i][col_] == 'X' or map_[row_+i][col_] == 'T':
                    continue
                elif map_[row_+i][col_] == 'S':
                    result = 'No'
                else:
                    break

        for i in range(1, n):

            # 열 위 감시
            if row_ - i < 0:
                break

            else:
                if map_[row_-i][col_] == 'X' or map_[row_-i][col_] == 'T':
                    continue
                elif map_[row_-i][col_] == 'S':
                    result = 'No'
                else:
                    break

        for i in range(1, n):

            # 행 오른쪽 감시
            if col_ + i > n-1 :
                break

            else:
                if map_[row_][col_+i] == 'X' or map_[row_][col_+i] == 'T':
                    continue
                elif map_[row_][col_+i] == 'S':
                    result = 'No'
                else:
                    break


        for i in range(1, n):

            # 행 왼쪽 감시
            if col_ - i < 0 :
                break

            else:
                if map_[row_][col_-i] == 'X' or map_[row_][col_-i] == 'T':
                    continue
                elif map_[row_][col_-i] == 'S':
                    result = 'No'
                else:
                    break
                    
    return result

# dfs 구현 : 장애물 설치의 모든 경우의 수에 대하여 고려하기 위한 함수
final_result = 'No'

def dfs(count):
    
    global final_result, count_c
    
    if count == 3 and moniter(map_) == 'Yes':
        final_result = 'Yes'
        return
    
    elif count == 3:
        return 
        
    for r_idx, row in enumerate(map_):
        for c_idx, col in enumerate(row):
                
            if map_[r_idx][c_idx] == 'X':
                map_[r_idx][c_idx] = 'O'
                count += 1
                dfs(count)
                
                map_[r_idx][c_idx] = 'X'
                count -= 1

dfs(0)
print(final_result)

# solution 2. combinations 함수를 이용한 풀이
# n 입력 받기
n = int(input())

# 복도 정보 입력 받기
map_ = []
for i in range(n):
    map_.append(list(map(str,input().split())))
    
# 복도 정보에서 선생님 좌표 찾기
T_coordis = []

for r_idx, row in enumerate(map_):
    for c_idx, col in enumerate(row):
        if map_[r_idx][c_idx] == 'T':
            T_coordis.append((r_idx, c_idx))

# 복도 정보에서 X의 좌표 찾기
X_coordis = []

for r_idx, row in enumerate(map_):
    for c_idx, col in enumerate(row):
        if map_[r_idx][c_idx] == 'X':
            X_coordis.append((r_idx, c_idx))

# moniter 함수 구현 : 선생님의 감시를 구현
def moniter(map_):

    result = 'Yes'

    for T_coordi in T_coordis:
        row_ = T_coordi[0]
        col_ = T_coordi[1]

        for i in range(1, n):

            # 열 아래 감시
            if row_ + i > n-1:
                break

            else:
                if map_[row_+i][col_] == 'X' or map_[row_+i][col_] == 'T':
                    continue
                elif map_[row_+i][col_] == 'S':
                    result = 'No'
                else:
                    break

        for i in range(1, n):

            # 열 위 감시
            if row_ - i < 0:
                break

            else:
                if map_[row_-i][col_] == 'X' or map_[row_-i][col_] == 'T':
                    continue
                elif map_[row_-i][col_] == 'S':
                    result = 'No'
                else:
                    break

        for i in range(1, n):

            # 행 오른쪽 감시
            if col_ + i > n-1 :
                break

            else:
                if map_[row_][col_+i] == 'X' or map_[row_][col_+i] == 'T':
                    continue
                elif map_[row_][col_+i] == 'S':
                    result = 'No'
                else:
                    break


        for i in range(1, n):

            # 행 왼쪽 감시
            if col_ - i < 0 :
                break

            else:
                if map_[row_][col_-i] == 'X' or map_[row_][col_-i] == 'T':
                    continue
                elif map_[row_][col_-i] == 'S':
                    result = 'No'
                else:
                    break
                    
    return result

# 파이썬의 조합 함수를 이용하여 가능한 O의 좌표 조합을 찾기
from itertools import combinations

def map_copy(map_list):
    
    copy_ = [[0]*n for _ in range(n)] 
    for r_idx, row in enumerate(map_list):
        for c_idx, col in enumerate(row):
            copy_[r_idx][c_idx] = map_list[r_idx][c_idx]
    
    return copy_


# 가능한 O의 조합들에 대하여 감시를 피할 수 있는지 계산
final_result = 'No'

for X_coordi in combinations(X_coordis,3):
    copy_map = map_copy(map_)

    for X_ in X_coordi:
        copy_map[X_[0]][X_[1]] = 'O'

    if moniter(copy_map) == 'Yes':
        final_result = 'Yes'
        
print(final_result)