감시 피하기 Python 정리 및 구현 (백준 18428)

감시 피하기

백준 18428: https://www.acmicpc.net/problem/18428

Edge case

1. 문제조건

• 벽생성의 경우: "O" 생성을 BFS로 진행해보면 좋을듯

---

Code

1. 1트

Combination + 구현

# 백준 18428
# https://www.acmicpc.net/problem/14888
# 삼성 기출
# 15:30 - 15:56 # 25분

# 1트 // 152ms (pypy3)

from copy import deepcopy

n = int(input())
graph = [list(input().split()) for _ in range(n)]

teacher = list()
student = list()
empties = list()
for r in range(n):
    for c in range(n):
        if graph[r][c] == 'T':
            teacher.append((r, c))
        elif graph[r][c] == 'S':
            student.append((r, c))
        else:
            empties.append((r, c))

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

#------------------------------------------#

def combinations(arr, n):
    result = []
    if n == 0:  # 종료조건
        return [[]]

    for i in range(len(arr)):
        elem = arr[i]
        rest_arr = arr[i+1:]
        for c in combinations(rest_arr, n-1):
            result.append([elem]+c)

    return result


# depth를 생각해서 몇번 이동할건지 곱하기로 연산해주기
# 1번째에 걸리면 이건 장애물 설치해도 안됨
def find():
    for tx, ty in teacher:
        for dir in range(4):  # 방향
            for j in range(1, n):   # 얼만큼 이동할지
                tnx, tny = tx + (dx[dir] * j), ty + (dy[dir] * j)
                if tnx < 0 or tnx >= n or tny < 0 or tny >= n or graph[tnx][tny] == 'O':
                    break
                if graph[tnx][tny] == 'S':
                    return 0
    return 1

if __name__ == "__main__":
    for empty in combinations(empties, 3):
        for x, y in empty:
            graph[x][y] = "O"
        
        if find():
            answer = "YES"
            break
        else:
            answer = "NO"
        
        for x, y in empty:
            graph[x][y] = "X"
    print(answer)