18428. 감시 피하기 (Python)

18428번: 감시 피하기

 

풀이

 리스트에 X의 위치를 담아두고 이를 조합을 사용하여 3개의 위치를 뽑아낸다. 조합으로 뽑아낸 3개의 위치에 장애물을 설치하고 선생님들의 위치에서 상하좌우를 봤을 때 학생을 볼 수 있는지를 체크한다.

 

코드

from itertools import combinations

# 범위 체크 함수
def isRange(x, y):
    return 0 <= x < N and 0 <= y < N

# 장애물 설치 후 선생님들의 위치에서 학생을 볼 수 있는지 없는지 체크 
def check():
    flag = True # flag가 True이면 학생들이 선생님들에게 들키지 않음을 의미 

    for (x, y) in teachers:
        if not flag: # 한 명의 학생이라도 선생님에게 보여진다면 탐색 종료 
            break

        for i in range(1, N):  # 오른쪽 체크
            nx = x + i

            if not isRange(nx, y) or board[nx][y] == 'T' or board[nx][y] == 'O':
                break
            if board[nx][y] == 'S':
                flag = False

        for i in range(1, N):  # 왼쪽 체크 
            nx = x - i

            if not isRange(nx, y) or board[nx][y] == 'T' or board[nx][y] == 'O':
                break
            if board[nx][y] == 'S':
                flag = False

        for i in range(1, N):  # 위쪽 체크 
            ny = y - i

            if not isRange(x, ny) or board[x][ny] == 'T' or board[x][ny] == 'O':
                break
            if board[x][ny] == 'S':
                flag = False

        for i in range(1, N):  # 아래쪽 체크 
            ny = y + i

            if not isRange(x, ny) or board[x][ny] == 'T' or board[x][ny] == 'O':
                break
            if board[x][ny] == 'S':
                flag = False

    return flag


# 장애물 설치 함수 
def setObstacles():
    for (x, y, z) in comList: # 조합으로 뽑아 낸 3개의 좌표에 장애물 설치 
        first, second, third = items[x], items[y], items[z]
        board[first[0]][first[1]] = 'O'
        board[second[0]][second[1]] = 'O'
        board[third[0]][third[1]] = 'O'

        # 장애물 설치 후 check 함수 실행하여 True이면 탐색 종료
        if check():
            global res
            res = 'YES'
            return

        # 다시 해당 좌표를 'X'로 되돌린다.
        board[first[0]][first[1]] = 'X'
        board[second[0]][second[1]] = 'X'
        board[third[0]][third[1]] = 'X'


if __name__ == '__main__':
    N = int(input())
    board = []
    items = [] # 'X'의 좌표들을 담아두기 위한 리스트 
    teachers = [] # 선생님들의 위치 좌표들을 담아두기 위한 리스트 

    res = 'NO'

    for i in range(N):
        tmp = list(map(str, input().split()))
        board.append(tmp)

        for j in range(N):
            if tmp[j] == 'X':
                items.append((i, j))
            elif tmp[j] == 'T':
                teachers.append((i, j))

    indices = [x for x in range(len(items))] # items에서 조합을 뽑아내기 위한 인덱스 리스트 
    comList = list(combinations(indices, 3)) # items에서 3개의 조합을 뽑아낸 리스트

    setObstacles()
    print(res)