[BOJ 18428] 감시 피하기

문제

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

18428번: 감시 피하기

 

 

접근 방법

• 3개의 위치를 선정하여 장애물을 놓고 그 장애물이 학생을 걸리지 않게 해 줄 수 있는지 판단하는 것이다. 즉, 문제는 2가지로 나눌 수 있다.
  • 첫 번째로 3개의 위치를 선정해야 한다.
  • 두 번째로 선정한 위치에 대해 감시를 피할 수 있는지 판정하는 로직을 넣어야 한다.
• N과 선생님의 전체 크기가 작고, 연산량 자체도 크지 않은 동시에 시간도 널럴하기 때문에 모든 위치에 대한 경우의 수를 고려할 수 있을 것이다.
• 3개의 위치를 선정하는 방법은 다음과 같이 구할 수 있다.
  • X에는 아무것도 없는 빈 공간이므로 장애물은 X에 배치할 수 있다. 이는 모든 X의 좌표를 넣고 그 중 3개를 뽑는 것으로 생각할 수 있을 것이다.
  • 이때 순서는 중요하지 않다. 순서를 바꾸어도 어차피 같은 위치에 장애물을 배치하는 것이기 때문에 순서를 무시한 모든 경우의 수를 가져야 한다. 즉 조합(combination)이 필요하다.
• 선정한 위치에 대해 감시를 피할 수 있는지 판정하는 것은 방향 벡터를 넣고 일직선으로 배열을 확인하는 방법을 사용하면 된다. 이때 일일히 선생님의 좌표를 판정하는 것은 귀찮기 때문에 미리 확인하여 따로 배열에 추가해 놓는다.
• 판정이 끝날 시 놓았던 장애물을 모두 제거하는 것도 필요하다.

 

 

풀이 코드

from itertools import combinations

N = int(input())
board = [list(map(str, input().split())) for _ in range(N)]

obj_location = []
teacher_location = []
for i in range(N):
    for j in range(N):
        if board[i][j] == 'X':
            obj_location.append([i, j])

        if board[i][j] == 'T':
            teacher_location.append([i, j])

arrangement = combinations(range(len(obj_location)), 3)
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]

for element in arrangement:
    can_fount = False
    loc1, loc2, loc3 = element

    board[obj_location[loc1][0]][obj_location[loc1][1]] = 'O'
    board[obj_location[loc2][0]][obj_location[loc2][1]] = 'O'
    board[obj_location[loc3][0]][obj_location[loc3][1]] = 'O'

    for t_location in teacher_location:
        for i in range(4):
            t_y, t_x = t_location
            while True:
                t_y += direction[i][0]
                t_x += direction[i][1]

                if t_y < 0 or t_y >= N or t_x < 0 or t_x >= N:
                    break

                if board[t_y][t_x] == 'S':
                    can_fount = True
                    break

                if board[t_y][t_x] == 'O':
                    break

            if can_fount:
                break
        if can_fount:
            break

    if not can_fount:
        print("YES")
        break

    board[obj_location[loc1][0]][obj_location[loc1][1]] = 'X'
    board[obj_location[loc2][0]][obj_location[loc2][1]] = 'X'
    board[obj_location[loc3][0]][obj_location[loc3][1]] = 'X'

else:
    print("NO")

• 모든 경우의 수에 대해 확인하며 backtrack을 하는 문제였다.