[백준] 감시 피하기 18428번 (python)

출처 : 18428번: 감시 피하기 (acmicpc.net)

18428번: 감시 피하기

풀이 방법

완전 탐색 + DFS로 풀이할 수 있다.

벽을 세우는 경우를 완전 탐색으로 푸는데 시간을 줄이기 위해 빈 공간을 미리 리스트에 저장해둔다

벽이 3개 생성되면 check 함수를 호출하여 각 선생님의 동서남북 방향을 검사한다 

while 문을 통해 board안에서의 동서남북중 한쪽씩 방향을 정해서 검사한다.

만약 검사 중 벽이 나타나면 다른 방향으로 넘어가고 검사중 학생이 나타나면 return false를 해준다

또는 좌표가 0 미만 이거나 N이하면 다른 방향으로 넘어 가주는 방식으로 검사한다

from sys import stdin
def check():
    for y, x in T:
        for i in range(4): ## 동서남북방향으로의 검사
            nextY = y + dy[i]
            nextX = x + dx[i]
            while (nextY >= 0 and nextX >= 0 and nextY < N and nextX < N): ## 범위 벗어 날때 까지 검사
                if board[nextY][nextX] == 'O': ## 벽이 나오는 경우
                    break
                if board[nextY][nextX] == 'S': ## 학생을 만나는 경우
                    return False
                nextY += dy[i] ## x, y 좌표 이동 (i에 맞는 인덱스 로만)
                nextX += dx[i]
    return True
def DFS(cnt, index):
    if cnt == 3:
        if(check()): ## 벽 3개 만들어 지면 체크하기
            print("YES" )
            exit()
        else:
            return
    for i in range(index, len(E)): ## 벽 세운후 DFS 호출하고 벽 초기화
        board[E[i][0]][E[i][1]] = 'O'
        DFS(cnt + 1, i + 1)
        board[E[i][0]][E[i][1]] = 'X'
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
board = [[]]
N = int(input())
T = []
E = []
board = [list(map(str, stdin.readline().split())) for _ in range(N)]
for i in range(N):
    for k in range(N):
        if board[i][k] == 'T': ## 선생님 위치 저장
            T.append([i, k])
        elif board[i][k] == 'X': ## 빈 공간 위치 저장
            E.append([i, k])
DFS(0, 0)
print("NO")