[DFS/BFS] 감시피하기

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 40 + a

1. 문제 설명

- 복도에 있는 선생님들을 피해 학생들이 야자를 째려고 한다. 학생들은 장애물 3개를 이용해서 선생님들의 시야를 가리고 탈출해야 한다. 선생님들은 상하좌우에 장애물이 없다면 끝까지 볼 수 있다. 

2. 접근 방식

- DFS나 BFS가 아닌 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))
            
def process():
    for x, y in teachers: 
        for i in range(4): # 4가지 방향 확인
            if watch(x, y, i): # 학생 발견하면 return True
                return True
    return False

def watch(x, y, direction): # [0, 1, 2, 3] #왼쪽, 오른쪽, 위쪽, 아래쪽
    if direction == 0:
        while y >= 0:
            if board[x][y] =="S": # 학생 발견하면 return True
                return True
            if board[x][y] == 'O': # 장애물 만나면 return False
                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

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" # 설치한 장애물 다시 없애기 (재귀와는 다르지만, 흐름은 비슷)
print("YES" if find else "NO")

4. 코멘트

- DFS를 사용해서 문제를 풀어보려고 했으나, 문제를 풀면 풀수록 헷갈려졌다.

- 문제의 원리를 이해한다면 크게 어렵지 않았겠지만, 새로운 함수를 만드는 과정에서 꽤 지쳤을 것 같다. (process(), whtch())

- 후반으로 갈 수록 리스트에 튜플 형태의 데이터를 넣는 경우가 훨씬 많아지는 것 같다.