[백준/bfs] 18428번: 감시 피하기

-문제: https://www.acmicpc.net/problem/18428

18428번: 감시 피하기

 

이전에 풀었던 연구실 문제와 풀이가 같다고 생각해서 그대로 풀다가 삽질했던 문제. 

마지막에는 메모리 초과까지 발생했다. 

 

문제 풀이 아이디어

1.  장애물을 설치하고

2. 선생님 주변에 학생이 있는지 확인

주변,확인 함수 구현 / process, watch 

3. 없으면 True 반환, 있으면 False 반환하고 

4. 그 값을 기준으로 답 출력 

 

연구실문제와 이 문제가  다른 점은 연구실 문제는 해당 위치 위,아래,좌,우만 보면 됐지만. 

여기는 한 방향에서 O나 S가 나올때까지 탐색을 할 수 있다는 점이다. 

이는 while i>=0 또는 while i<n 형태로 구현하면 된다 

 

선생님 시야에 학생이 들어온다면 process는 False를 반환한다. 

만약 아니라면 True를 반환하고, 이 경우에 YES를 출력, 아니면 NO를 출력한다. 

 

무작위로 하는 경우에는 항상 연산 끝나고 되돌려 놓기 

for data in combinations(spaces,3):
    for x,y in data:
        board[x][y]='O'

    if not process():
        find=True
        break
    for x,y in data:
        board[x][y]='X'

 

-정답풀이

from itertools import combinations
n=int(input())
board=[]
teachers=[]
spaces=[]

for i in range(n):
    board.append(list(input().split()))
    for j in range(n):
        if board[i][j]=='T':
            teachers.append((i,j))
        if board[i][j]=='X':
            spaces.append((i,j))
            
def watch(x,y,direction):
    if direction ==0:
        while y>=0:
            if board[x][y]=='S':
                return True
            if board[x][y]=='O':
                return False
            y-=1
    if direction ==1:
        while y<n:
            if board[x][y]=='S':
                return True
            if board[x][y]=='O':
                return False
            y+=1
            
    if direction ==2:
        while x>=0:
            if board[x][y]=='S':
                return True
            if board[x][y]=='O':
                return False
            x-=1
    if direction ==3:
        while x<n:
            if board[x][y]=='S':
                return True
            if board[x][y]=='O':
                return False
            x+=1
    return False

def process():
    for x,y in teachers:
        for i in range(4):
            if watch(x,y,i):
                return True
    return False 
    
find=False
for data in combinations(spaces,3):
    for x,y in data:
        board[x][y]='O'

    if not process():
        find=True
        break
    for x,y in data:
        board[x][y]='X'
if find:
    print('YES')
else:
    print('NO')