[백준] 18428 : 감시 피하기 python

 

 

 

1.  n을 입력받는다.
2. 그래프 정보를 입력받는다.
   1. 탐색할 때 활용하기 위해 선생님의 (행, 열)값을 teachers라는 리스트에 저장한다.
3. 선생님의 위치에서 상하좌우 방향으로 감시하는 함수 watch(x,y)를 구현한다.
   
   1. for문으로 그래프 범위를 벗어나지 않는 선에서 탐색을 하다가 학생을 발견하면 True를 반환한다.
4.  감시 성공여부를 뜻하는 전역변수 answer를 False로 초기화한다. 이후에 감시를 피하는 데에 성공하면 True로 업데이트한다. 
5. DFS함수를 구현한다.
   1. 시간제한이 넉넉하니 최대 6x6인 그래프에 장애물을 하나씩 세우고 장애물의 개수가 3이 되면 teachers에 저장된 선생님들의 위치에서 상하좌우감시함수를 수행한다.
   2. 선생님이 감시를 실패할 때마다 teacher_cnt를 증가시킨다.
   3. teacher_cnt가 len(teachers)와 일치하면 감시를 피할 수 있다는 의미이므로 전역변수 answer을 True로 업데이트한 뒤 함수를 종료한다.
6. answer이 True면 "YES"를 False면 "NO"를 출력한다.

 

코드

n = int(input())
data = []
teachers = []
for i in range(n):
    data.append(list(input().split()))
    for j in range(n):
        if data[i][j]=='T':
            teachers.append((i,j))
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def watch(x,y):
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        
        # nx, ny가 범위를 벗어나지 않고 O가 아닐 때까지
        while 0<=nx<n and 0<=ny<n and data[nx][ny]!='O':
        	# 학생이라면 감시를 성공했으니 True를 반환
            if data[nx][ny]=='S':
                return True
            else:
                nx += dx[i]
                ny += dy[i]
    # 감시를 피했다면 False를 반환
    return False

def dfs(cnt):
    global answer
    # 3개의 벽을 다 세웠다면 감시를 해봐야 함
    if cnt == 3:
    	# 선생님의 감시를 피했을 때마다 1씩 증가시킬 변수
        teacher_cnt = 0
        # 선생님들의 위치에서 감시를 수행함
        for x,y in teachers:
        	# 감시를 피했다면 teacher_cnt 를 1 증가시킴
            if not watch(x,y):
                teacher_cnt +=1
            # 감시를 피하지 못했다면 더 할 필요 없음
            else:
                break
        # 모든 선생님의 감시를 피하는 데에 성공했다면
        if teacher_cnt==len(teachers):
            answer = True
            return
                
        return
    
    for i in range(n):
        for j in range(n):
            # 빈칸에 벽을 세우고 dfs를 호출
            if data[i][j]=='X':
                data[i][j] = 'O'
                cnt +=1
                dfs(cnt)
                data[i][j] = 'X'
                cnt -= 1

answer = False
dfs(0)

# 감시를 피하는 데에 성공했으면 YES 아니면 NO 출력 
if answer:
    print("YES")
else:
    print("NO")