감시 피하기

 

 

 

 

유형 파악 및 분석

이 문제는 내 생각엔 구현이 까다로워 구현문제에 가까운 것 같다.

정리를 해보자면 까다로운 구현 + BFS를 통한 감시정도 되는 것 같다.

 

차분히 구현해야 하며, 구현 과정을 정리하면 아래와 같다.

 

1. 입력 받음과 동시에, 나중에 맵 초기화를 위한 선생위치, 학생위치, 빈칸위치를 리스트에 담아둔다.

2. 조합을 통해 빈칸위치들 중에서 장애물의 조합을 구한다.

3. 장애물마다 설치하고 감시하고 장애물을 해체하는 과정을 반복한다.

4. 감시 과정은 미리 담아둔 선생위치를 하나씩 꺼내 확인한다.

 

감시는 학생 발견시 return True를 때려 하던 과정 멈추고 다음 장애물을 확인하기 위해 넘어가게 설정해 두었다.

 

 

코드

graph = []
x_pos = []
t_pos = []
s_pos = []

n = int(input())
for i in range(n):
    graph.append(list(input().split()))
    for j in range(n):
        if graph[i][j] == 'X':
            x_pos.append([i, j])
        if graph[i][j] == 'T':
            t_pos.append([i, j])
        if graph[i][j] == 'S':
            s_pos.append([i, j])


from itertools import combinations
o_pos = list(combinations(x_pos, 3))



def find_by_direction(x, y, direction):
    if direction == 0: # 북
        if x-1 < 0 or graph[x-1][y] == 'O':
            return False
        if graph[x-1][y] == 'S':
            return True
        if graph[x-1][y] == 'T' or graph[x-1][y] == 'X':
            return find_by_direction(x-1, y, direction)
    elif direction == 1: # 서
        if y-1 < 0 or graph[x][y-1] == 'O':
            return False
        if graph[x][y-1] == 'S':
            return True
        if graph[x][y-1] == 'T' or graph[x][y-1] == 'X':
            return find_by_direction(x, y-1, direction)
    elif direction == 2: # 남
        if x+1 >= n or graph[x+1][y] == 'O':
            return False
        if graph[x+1][y] == 'S':
            return True
        if graph[x+1][y] == 'T' or graph[x+1][y] == 'X':
            return find_by_direction(x+1, y, direction)
    else: # 동 
        if y+1 >= n or graph[x][y+1] == 'O':
            return False
        if graph[x][y+1] == 'S':
            return True
        if graph[x][y+1] == 'T' or graph[x][y+1] == 'X':
            return find_by_direction(x, y+1, direction)


dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
def find_student(x, y):
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if next_x < 0 or next_x >= n or next_y < 0 or next_y >= n:
            continue
        if graph[next_x][next_y] == 'O':
            continue
        if graph[next_x][next_y] == 'S':
            return True
        direction = i
        if graph[next_x][next_y] == 'T' or graph[next_x][next_y] == 'X':
            if find_by_direction(next_x, next_y, direction):
                return True
    return False



for obstacles in o_pos:
    for obstacle in obstacles:
        graph[obstacle[0]][obstacle[1]] = 'O'

    continue_check = True
    for t in t_pos:
        if find_student(t[0], t[1]):
            continue_check = False
            break
    
    if continue_check:
        for i in graph:
            print(i)
        break
    
    for obstacle in obstacles:
        graph[obstacle[0]][obstacle[1]] = 'X'