[백준] 18428 파이썬(python) : 감시 피하기 - (★)

18428번 : 감시 피하기

 

 

 

import sys
n = int(sys.stdin.readline())
graph = [ list(sys.stdin.readline().rstrip().split()) for _ in range(n) ] #1
teacher = 0 #2
for i in range(n):
    teacher += graph[i].count('T') #3
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]
def view(x, y): #4
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        while 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != 'O': #5
            if graph[nx][ny] == 'S': #6
                return False
            else: #7
                nx += dx[i]
                ny += dy[i]
    return True #8
def backTracking(depth):
    global answer
    if depth == 3: #9
        cnt = 0
        for i in range(n):
            for j in range(n):
                if graph[i][j] == 'T': #10
                    if view(i, j) == True: #11
                        cnt += 1
        if cnt == teacher: #12
            answer = True
        return
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 'X': #13
                graph[i][j] = 'O'
                backTracking(depth+1)
                graph[i][j] = 'X'
answer = False
backTracking(0)
if answer: #14
    print('YES')
else:
    print('NO')

 

#1 : 그래프 입력

#2 : 선생님의 수 저장할 변수

#3 : 그래프 탐색하면서 'T'의 숫자만큼 teacher 변수에 개수 추가

#4 : 선생님의 시야를 확인해줄 함수

#5 : 4방향 중 n의 범위 안에 들어오고 장애물 'O'가 없는 경우

#6 : 'S'를 만난경우 선생님의 감시 피하기에 실패 했으므로 False를 리턴

#7 : 만나지 않았다면 같은 방향으로 선생님의 시야를 한칸 더 전진

#8 : 4방향을 모두 확인했는데 'S'를 찾지 못한경우(반복문이 끝날때까지 못찾았을때) True를 리턴

#9 : 백트래킹 함수를 실행할때 설치한 장애물의 수가 3개일때

#10 : 그래프를 돌다가 'T'를 만나면

#11 : view함수를 실행하고 리턴값이 True라면(선생님의 감시를 피했다면) cnt +1

#12 : 그래프 순환이 끝나고 선생님의 감시를 피한 횟수가 선생님의 수와 일치한다면 answer변수를 True로 갱신

#13 : 장애물 설치가 3개가 아닐때 그래프를 돌면서 'X'가 나오면 장애물('O') 설치하면서 백트래킹 재귀호출

#14 : 선생님의 감시를 모두 피했다는 변수 answer가 True라면 'YES' 출력 아니라면 'NO' 출력

 

---

14502번 : 연구소