[Implementation] 이코테 “감시 피하기” Python 풀이

문제

• NxN 크기의 복도가 있다.
• 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다.
• 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복도로 빠져나온 학생들은 선생님의 감시에 들키지 않는 것이 목표이다.
• 각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행한다.
• 단, 복도에 장애물이 위치한 경우, 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다.
• 또한 선생님은 상, 하, 좌, 우 4가지 방향에 대하여, 아무리 멀리 있더라도 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다고 가정하자.
• 다음과 같이 3x3 크기의 복도의 정보가 주어진 상황을 확인해보자.
• 본 문제에서 위치 값을 나타낼 때는 (행,열)의 형태로 표현한다.
• 선생님이 존재하는 칸은 T, 학생이 존재하는 칸은 S, 장애물이 존재하는 칸은 O로 표시하였다.
• 아래 그림과 같이 (3,1)의 위치에는 선생님이 존재하며 (1,1), (2,1), (3,3)의 위치에는 학생이 존재한다.
• 그리고 (1,2), (2,2), (3,2)의 위치에는 장애물이 존재한다.

• 이 때 (3,3)의 위치에 존재하는 학생은 장애물 뒤편에 숨어 있기 때문에 감시를 피할 수 있다.
• 하지만 (1,1)과 (2,1)의 위치에 존재하는 학생은 선생님에게 들키게 된다.
• 학생들은 복도의 빈 칸 중에서 장애물을 설치할 위치를 골라, 정확히 3개의 장애물을 설치해야 한다.
• 결과적으로 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지 계산하고자 한다.
• NxN 크기의 복도에서 학생 및 선생님의 위치 정보가 주어졌을 때, 장애물을 정확히 3개 설치하여 모든 학생들이 선생님들의 감시를 피하도록 할 수 있는지 출력하는 프로그램을 작성하시오.
• 예를 들어 N=5일 때, 다음과 같이 선생님 및 학생의 위치 정보가 주어졌다고 가정하자.

• 이 때 다음과 같이 3개의 장애물을 설치하면, 모든 학생들을 선생님의 감시로부터 피하도록 만들 수 있다.

입력 조건

• 첫째 줄에 자연수 N이 주어진다. (3 ≤ N ≤ 6)
• 둘째 줄에 N개의 줄에 걸쳐서 복도의 정보가 주어진다.
• 각 행에서는 N개의 원소가 공백을 기준으로 구분되어 주어진다.
• 해당 위치에 학생이 있다면 S, 선생님이 있다면 T, 아무것도 존재하지 않는다면 X가 주어진다.
• 단, 전체 선생님의 수는 5이하의 자연수, 전체 학생의 수는 30이하의 자연수이며 항상 빈 칸의 개수는 3개 이상으로 주어진다.

출력 조건

• 첫째 줄에 정확히 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지의 여부를 출력한다.
• 모든 학생들을 감시로부터 피하도록 할 수 있다면 "YES", 그렇지 않다면 "NO"를 출력한다.

입력 예시

5
X S X X T
T X S X X
X X X X X
X T X X X
X X T X X

4
S S S T
X X X X
X X X X
T T T X

출력 예시

YES

NO

풀이

• 이 문제는 장애물을 정확히 3개 설치하는 모든 경우를 확인하여, 매 경우마다 모든 학생을 감시로부터 피하도록 할 수 있는지의 여부를 출력해야 한다.
• 장애물을 설치하는 모든 조합을 찾기 위해선, DFS/BFS를 사용해 모든 조합을 반환하는 함수를 작성하거나, 파이썬의 조합 라이브러리를 사용해 구할 수 있다.
• 현재 설치된 장애물을 기준으로, 선생님이 학생을 감지할 수 있는지의 여부를 판단하는 check 함수와
• 선생님의 위치를 기준으로 특정 방향으로 감시를 진행하는 watch 함수를 별도로 구현했으며,
• 세부 알고리즘은 아래 예제 코드와 같다.

예제 코드

# https://www.acmicpc.net/problem/18428

import sys
from itertools import combinations

# 복도 크기 입력
n = int(sys.stdin.readline())
# 복도 정보
hallway = []
# 선생님 위치
teachers = []
# 빈칸 위치
emptys = []

# 복도 정보 입력
for i in range(n):

    row = sys.stdin.readline().split()
    hallway.append(row)

    for j in range(n):
        # 장애물을 설치할 수 있는 (빈 공간) 위치 저장
        if (row[j] == 'X'):
            emptys.append((i, j)) 
        # 선생님이 존재하는 위치 저장
        elif (row[j] == 'T'):
            teachers.append((i, j)) 

# 선생님의 위치 x, y를 기준으로 direction 방향으로 감시를 진행 (학생 발견 : True, 학생 미발견 : False)
def watch(x, y, direction):
    if direction == 0: #동쪽
        while (y < n):
            if (hallway[x][y] == 'O'): # 장애물이 있는 경우
                return False
            if (hallway[x][y] == 'S'): # 학생이 있는 경우
                return True
            y += 1
    if direction == 1: #서쪽
        while (y >= 0):
            if (hallway[x][y] == 'O'): # 장애물이 있는 경우
                return False
            if (hallway[x][y] == 'S'): # 학생이 있는 경우
                return True
            y -= 1
    if direction == 2: #남쪽
        while (x < n):
            if (hallway[x][y] == 'O'): # 장애물이 있는 경우
                return False
            if (hallway[x][y] == 'S'): # 학생이 있는 경우
                return True
            x += 1
    if direction == 3: #북쪽
        while (x >= 0):
            if (hallway[x][y] == 'O'): # 장애물이 있는 경우
                return False
            if (hallway[x][y] == 'S'): # 학생이 있는 경우
                return True
            x -= 1

    # 학생 미발견
    return False

# 현재 장애물 조합이 있을 때, 학생을 감지할 수 있는지
def check():

    # 모든 선생님의 위치를 하나씩 확인
    for x, y in teachers:

        # 각 선생님이 4가지 방향으로 학생을 감지할 수 있는지 확인
        for i in range(4):
            # 학생을 감지할 수 있다면
            if (watch(x, y, i)):
                return True
    # 감지 불가능
    return False

# 빈칸 위치들 중, 3개의 장애물 조합 계산
emptys_total_combi = list(combinations(emptys, 3))

# 학생이 한 명도 감지되지 않도록 설치할 수 있는지의 여부
find = False

# 장애물 설치 조합에 따라, 선생님이 상, 하, 좌, 우로 학생들을 감시할 수 있는지 확인
for emptys_combi in emptys_total_combi:

    # 장애물 설치
    for x, y in emptys_combi:
        hallway[x][y] = 'O'

    # 해당 장애물 조합을 통해 학생을 감지할 수 없었다면
    if (check() == False):
        find = True
        break

    # 장애물 제거
    for x, y in emptys_combi:
        hallway[x][y] = 'X'

if (find == True):
    print("YES")
else:
    print("NO")

참고

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