[이코테] DFS/BFS - 감시 피하기

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

18428번: 감시 피하기

사고과정

• 저번에 풀어본 DFS로 완전탐색을 구하는 연구소 문제와 비슷한 유형인 것 같았다. 주어진 데이터 범위도 적고 완전탐색으로 해결할 것이라는 것은 잘 예상했다. 그래서 연구소 문제처럼 DFS로 풀려고 했지만 DFS 재귀함수로 구현하면 중간에 감시 피하는 방법을 찾았을 때 바로 break 할 수 있는 방법을 찾지 못해서 완벽하게 풀지는 못했다..
• 풀이를 보니 완전탐색이여서 DFS를 사용할 수 도 있었지만 조합 라이브러리를 사용했다. 나와 다르게 풀었던 점은 연구소 문제처럼 영역의 넓이같은 것을 구하는 것이 아니라 좌표값들만 있어도 되기 때문에 학생들, 선생님들, 빈 공간에 대한 좌표들을 개별로 리스트로 담았다. 2차원 리스트 운영은 새로운 벽 3개를 설치한 후의 맵 정보와 그 맵 정보로 선생님들이 상,하,좌,우 감시했을 때 학생들이 있는지 없는지, 장애물이 있는지, 맵 바깥을 벗어나는지 판단하는 용도로만 썼다.(나는 모든 것을 2차원 리스트로 운영하려고 했다..)
• 좌표값들을 리스트에 담아서 해결한 풀이방법은 저번에 풀어본 [구현]-기둥과 보 설치 문제와 유사했다.

풀이(스스로 못 푼 풀이)

from itertools import combinations

n = int(input())
data = []
teachers = []
students = []
spaces = []
for i in range(n):
    array = list(input().split())
    data.append(array)
    for j in range(n):
        if array[j] == 'X': # 빈 공간
            spaces.append((i, j))
        if array[j] == 'T': # 선생님
            teachers.append((i, j))
        if array[j] == 'S': # 학생
            students.append((i, j))

def watch(x, y, direction):
    if direction == 0:  # 왼쪽만 탐색
        while y >= 0:
            if data[x][y] == 'S':
                return True
            if data[x][y] == 'O':
                return False
            y -= 1
    if direction == 1:  # 오른쪽만 탐색
        while y < n:
            if data[x][y] == 'S':
                return True
            if data[x][y] == 'O':
                return False
            y += 1
    if direction == 2:  # 위쪽만 탐색
        while x >= 0:
            if data[x][y] == 'S':
                return True
            if data[x][y] == 'O':
                return False
            x -= 1
    if direction == 3:   # 아래쪽만 탐색
        while x < n:
            if data[x][y] == 'S':
                return True
            if data[x][y] == 'O':
                return False
            x += 1
    return False  # 좌표가 맵 밖으로 나가게 되면

def process():
    # 선생님 감시 시작
    for x, y in teachers:
        # 선생님 당 4가지 방향으로 감시 시작
        for i in range(4):
            if watch(x, y, i):
                return True
    return False

# 벽 3개를 설치하는 경우의 수 모두 탐색
flag = False
for comb in list(combinations(spaces, 3)):
    # 벽 3개 설치
    for x, y in comb:
        data[x][y] = 'O'
    # 벽 3개 설치한 후, 선생님들 감시 시작
    if not process():
        flag = True
        break
    # 설치한 벽 3개 다시 제거
    for x, y in comb:
        data[x][y] = 'X'

if flag:
    print('YES')
else:
    print('NO')