[BOJ] Q18428 감시피하기

[BOJ] Q18428 감시피하기

Question

Language: Python

Difficulty: Silver 1

해당 문제는 이전에 풀었던 Q14502와 매우 유사하다

bfs 모두 수행한 후 학생들이 제대로 숨어있는지 확인하는 과정에서 선생님들은 동,서,남,북에 대해 학생들이 시야에 존재하는 지 확인하게 된다.

이때, 만약 시야에 장애물이 보이면 장애물 너머의 학생은 가려지게 된다. 따라서 해당 방향으로는 더 이상 탐색을 진행하지 않아도 된다.

Solution

def checkIfTrue():
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]

    for row,col in teacher_locations:
        for dir in range(4):
            for times in range(n):
                new_row=row+dy[dir]*times
                new_col=col+dx[dir]*times

                if new_row < 0 or new_row >=n or new_col < 0 or new_col >=n:
                    break
                elif map_data[new_row][new_col] == 'S':
                    return False
                elif map_data[new_row][new_col] == 'O':
                    break   

    return True

def dfs(count):
    global answer
    for row in range(n):
        for col in range(n):
            if count==3:
                if checkIfTrue():
                    answer='YES'
                    return
                else:
                    return

            if map_data[row][col]=='X':
                map_data[row][col]='O'
                dfs(count+1)
                map_data[row][col]='X'   

answer='NO'
map_data=[]
n=int(input())
teacher_locations=[]
for row in range(n):
    map_data.append(list(map(str,input().split())))
    for col in range(n):
        if map_data[row][col] == 'T':
            teacher_locations.append((row,col))

dfs(0)
print(answer)