문제

BOJ 18428: 감시 피하기 https://www.acmicpc.net/problem/18428

풀이

조건

• 각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행한다.
• 단, 복도에 장애물이 위치한 경우, 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다.
• 선생님은 상, 하, 좌, 우 4가지 방향에 대하여, 아무리 멀리 있더라도 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다고 가정한다.
• 선생님이 존재하는 칸은 T, 학생이 존재하는 칸은 S, 장애물이 존재하는 칸은 O로 표시한다.
• 복도의 빈 칸 중에서 장애물을 설치할 위치를 골라, 정확히 3개의 장애물을 설치해야 한다. 결과적으로 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지 계산한다.

풀이 순서

• DFS를 사용한다.
• 장애물이 없을 때의 Teacher 시야를 체크해 저장해둔다.
• 학생들의 모든 좌표를 저장해둔다.
• 'X'(빈자리)이고 Teacher의 시야가 닿는 위치에 장애물을 하나씩 놓으며 재귀호출을 한다.
• 장애물을 3개 놨을 때 장애물을 놓은 상태에서 Teacher의 시야를 다시 체크해 결과를 확인한다.

코드

Python

# Teacher가 볼 수 있는 시야를 체크하는 함수
def check_t_sight(plain_board):
    t_sight = [[False for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if plain_board[i][j] == 'T':
                # 세로로 시야 체크
                for a in range(i - 1, -1, -1):
                    if plain_board[a][j] == 'O':
                        break
                    t_sight[a][j] = True
                for a in range(i + 1, N, 1):
                    if plain_board[a][j] == 'O':
                        break
                    t_sight[a][j] = True
                for b in range(j - 1, -1, -1):
                    if plain_board[i][b] == 'O':
                        break
                    t_sight[i][b] = True
                for b in range(j + 1, N, 1):
                    if plain_board[i][b] == 'O':
                        break
                    t_sight[i][b] = True

    return t_sight


# 장애물을 놓는 경우를 구하는 함수
def make_object_case(depth, sight_board, n_board, o_pos):
    global board # 원본 상태가 저장된 배열
    global s_pos # 학생 좌표 들어있는 배열
    global check # 결과 저장할 배열
    # 장애물을 3개 놨으면
    if depth == 3:
        # 새로운 teacher 시야 체크
        n_t_sight = check_t_sight(n_board)
        # 시야 안에 학생 있는지 체크
        for pos in s_pos:
            if n_t_sight[pos[0]][pos[1]]:
                check.append(False)
                return

        check.append(True)
        return

    for i in range(N):
        for j in range(N):
            # 빈 자리 and teacher 시야가 닿은 위치
            if board[i][j] == 'X' and sight_board[i][j] == True:
                n_board[i][j] = 'O' # 현재 위치에 장애물 놓기
                o_pos.append([i, j]) # 놓은 장애물 좌표 저장
                
                # 재귀로 다음 장애물 위치 탐색
                make_object_case(depth + 1, sight_board, n_board, o_pos)

                o_pos.pop() # 다음 탐색을 위해 장애물 제거
                n_board[i][j] = 'X' # 현재 위치 비우기


N = int(input())
# 초기 상태 입력
board = [list(map(str, input().split())) for _ in range(N)]

# 장애물이 없을 때 teacher 시야 체크
plain_sight = check_t_sight(board)

# 학생 좌표 구하기
s_pos = []
for i in range(N):
    for j in range(N):
        if board[i][j] == 'S':
            s_pos.append([i, j])

# teacher 시야 안에 Object 3개 놔서 teacher 시야 확인
check = []  # 장애물 3개 놓은 경우마다 나온 결과를 저장할 배열
o_pos = []  # 장애물 놓은 좌표 저장할 배열
# 결과를 찾는 함수
make_object_case(0, plain_sight, board, o_pos)

if True in check:
    print('YES')
else:
    print('NO')

정리

• DFS를 사용해 해결했다.
• 재귀 호출을 할 때 make_object_case(depth, sight_board, n_board, o_pos) 함수를 사용했는데 파라미터를 더 줄일 수 있지 않을까 고민을 많이 했다.