[이코테] 완전탐색 - 감시피하기 with 파이썬

1. 문제

• 백준 18428과 동일한 문제
  - 링크

• N x N 크기의 복도

• 선생님 , 학생, 장애물

• 선생님들 , 상하좌우 4방향으로 감시 진행

  • 장애물이 위치한 경우 장애물 뒤편에 숨은 학생은 볼 수 없다.
  • 장애물이 없다면 아무리 멀어도 학생들을 볼 수 있다.

• 선생님 T, 학생 S, 장애물 O

• 학생 , 3개의 장애물 설치

• 3개의 장애물 설치하여, 모든 학생들이 감시를 피하도록 할 수 있는지 계산

• 입력

  • N 복도 크기
  • 복도에 선생님과, 학생 위치

• 출력

  • 감시를 피할 수 있다면 YES, 그렇지 않다면 NO 출력

입출력 예시

2. 아이디어

• 장애물을 combinations로 설치하여, 모든 경우에 대해서 학생을 찾을 수 있는지 탐색한다. 학생을 찾는 것을 구현하지 못해서, 책을 리뷰하였다.

3. 예제코드

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))
            
# 감시 함수  , 학생 발견 True, 미발견 False
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 # 모두 탐색했는데, S가 없었으면, 미발견

# 모든 선생님 사방 감시 함수, 사방 중 한곳이라도 나오면 True, 아니면 False
def process():
    for x, y in teachers:
        # 사방 탐색 
        for i in range(4):     # 사방 탐색 중 발견되면 
            if watch(x,y,i):
                return True
    return False   # 발견 안되면 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')         

참조

• 이것이 취업을 위한 코딩테스트다. with 파이썬