15683 - 감시*

처음에는 각 경우의 수에 따라서 for와 if문으로 전개하다보니 시간초과가 나왔다. 

import copy
        
def rotate(graph, num, r, c, article):
    # 0 : 고정, 1 : 90도 회전, 2 : 180도 회전, 3 : 270도 회전
    if num == 1:
        # 오른쪽
        if article == 0:
            i = c+1
            while i < M and graph[r][i] != 6:
                if graph[r][i] == 0:
                    graph[r][i] = 'x'
                else:
                    break
                i += 1
        # 아래쪽
        elif article == 1:
            i = r+1
            while i < N and graph[i][c] != 6:
                if graph[i][c] == 0:
                    graph[i][c] = 'x'
                else:
                    break
                i += 1
        # 왼쪽
        elif article == 2:
            i = c - 1
            while i >= 0 and graph[r][i] != 6:
                if graph[r][i] == 0:
                    graph[r][i] = 'x'
                else:
                    break
                i -= 1
        # 위쪽
        elif article == 3:
            i = r-1
            while i >= 0 and graph[i][c] != 6:
                if graph[i][c] == 0:
                    graph[i][c] = 'x'
                else:
                    break
                i -= 1

    elif num == 2:
        if article == 0 or article == 2:
            i = c-1
            # 왼쪽
            while i >= 0 and graph[r][i] != 6:
                if graph[r][i] == 0:
                    graph[r][i] = 'x'
                else:
                    break
                i-=1
            j = c+1
            # 오른쪽
            while j < M and graph[r][j] != 6:
                if graph[r][j] == 0:
                    graph[r][j] = 'x'
                else:
                    break
                j+=1
        elif article == 1 or article == 3:
            i = r-1
            # 위쪽
            while i >= 0 and graph[i][c] != 6:
                if graph[i][c] == 0:
                    graph[i][c] = 'x'
                else:
                    break
                i -= 1

            j = r+1
            # 아래쪽
            while j < N and graph[j][c] != 6:
                if graph[j][c] == 0:
                    graph[j][c] = 'x'
                else:
                    break
                j += 1

    elif num == 5 or num == 4:
        i = c - 1
        # 왼쪽
        while i >= 0 and graph[r][i] != 6:
            if graph[r][i] == 0:
                graph[r][i] = 'x'
            else:
                    break
            i -= 1
        j = c + 1
        # 오른쪽
        while j < M and graph[r][j] != 6:
            if graph[r][j] == 0:
                graph[r][j] = 'x'
            else:
                    break
            j += 1

        k = r - 1
        # 위쪽
        while k >= 0 and graph[k][c] != 6:
            if graph[k][c] == 0:
                graph[k][c] = 'x'
            else:
                    break
            k -= 1

        l = r + 1
        # 아래쪽
        while l < N and graph[l][c] != 6:
            if graph[l][c] == 0:
                graph[l][c] = 'x'
            else:
                    break
            l += 1

        if num == 4:
            # 아래쪽 해당X
            if article == 0:
                i = r+1
                while i < N and graph[i][c] == 'x':
                    graph[i][c] = 0
                    i+=1

            # 왼쪽 해당X
            elif article == 1:
                i = c - 1
                while i >= 0 and graph[r][i] == 'x':
                    graph[r][i] = 0
                    i -= 1

            # 위쪽 해당X
            elif article == 2:
                i = r - 1
                while i >= 0 and graph[i][c] == 'x':
                    graph[i][c] = 0
                    i -= 1

            # 오른쪽 해당X
            elif article == 3:
                i = c + 1
                while i < M and graph[r][i] == 'x':
                    graph[r][i] = 0
                    i += 1
    return graph

def countX(graph):
    area = 0
    for rList in graph:
        area += rList.count(0)
    return area

def rotateCCTV(tfList):
    global graph, cctv, maxArea

    # 회전X, 90도 회전, 180도 회전, 270도 회전
    for i in range(4):
        copyGraph = copy.deepcopy(graph)
        for idx in range(len(tfList)):
            if tfList[idx] == True:
                copyGraph = rotate(copyGraph, cctv[idx][0], cctv[idx][1], cctv[idx][2], i)
            else:
                copyGraph = rotate(copyGraph, cctv[idx][0], cctv[idx][1], cctv[idx][2], 0)
        maxArea = min(maxArea, countX(copyGraph))

    return maxArea

def tfPermutation(n):
    if visited.count(True) == n:
        maxArea = rotateCCTV(visited)
        return

    for i in range(len(visited)):
        if visited[i] == False:
            visited[i] = True
            tfPermutation(n)
            visited[i] = False

# 0 : 빈칸, 6 : 벽, 1~5 : CCTV 번호
# 1 : 오른쪽, 2 : 좌우, 3 : 상우, 4 : 좌우상, 5 : 상하좌우
# 회전 : 90도씩 가로 또는 세로
# CCTV의 개수는 8개 이하

# CCTV 방향을 적절히 정해서 사각지대의 최소 크기를 구하는 프로그램 -> CCTV 감시 영역의 최대 영역
N, M = map(int, input().split())
graph = []
# cctv 위치 & 번호
cctv =[]
# wall 벽의 위치
wall = []
for r in range(N):
    temp = list(map(int, input().split()))
    graph.append(temp)
    for c, num in enumerate(temp):
        if 0<num<=5:
            cctv.append([num, r, c])
visited = [False] * len(cctv)
maxArea = 64

for n in range(len(cctv)+1):
    tfPermutation(n)
print(maxArea)

재귀함수에 익숙해졌다고 생각했는데... 문제를 풀면서 재귀함수로 짜려고 하면 쉽게 상상?이 안간다.

일부로 dfs로 풀어보는 연습이 필요할 것 같다.

import copy
def chkArea(board, move, r, c):
    for m in move:
        dr = r; dc = c
        # 볼 수 있는 방향 모두 벽이 있거나 넘어가기 전까지 'x'확장
        while True:
            dr = dx[m] + dr; dc = dy[m] + dc
            print(dr, dc)
            if dr < 0 or dc < 0 or dr >= N or dc >= M:
                break
            elif board[dr][dc] == 6:
                break
            elif board[dr][dc] == 0:
                board[dr][dc] = 'x'

# [[0], [1], [2], [3]] : 1번
# [[0, 2], [1, 3]], : 2번
# [[0, 1], [1, 2], [2, 3], [3, 0]], : 3번
# [[3, 0, 1], [0, 1, 2], [1, 2, 3], [2, 3, 0]], : 4번
# [[0, 1, 2, 3]]] : 5번
def dfs(graph, n):
    global minArea
    if n == len(cctv):
        area = 0
        for i in range(N):
            area += graph[i].count(0)
        minArea = min(area, minArea)
        return

    copyGraph = copy.deepcopy(graph)
    num = cctv[n][0]; r = cctv[n][1]; c = cctv[n][2]
    for move in mode[num]:
        chkArea(copyGraph, move, r, c)
        dfs(copyGraph, n+1)
        # 원상복구
        copyGraph = copy.deepcopy(graph)

# 0 : 빈칸, 6 : 벽, 1~5 : CCTV 번호
# 1 : 오른쪽, 2 : 좌우, 3 : 상우, 4 : 좌우상, 5 : 상하좌우
# 회전 : 90도씩 가로 또는 세로
# CCTV의 개수는 8개 이하

# CCTV 방향을 적절히 정해서 사각지대의 최소 크기를 구하는 프로그램 -> CCTV 감시 영역의 최대 영역
if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = []
    # cctv 위치 & 번호
    cctv = []
    for r in range(N):
        temp = list(map(int, input().split()))
        graph.append(temp)
        for c, num in enumerate(temp):
            if 0 < num <= 5:
                cctv.append([num, r, c])
    minArea = 64

    # 상, 우, 하, 좌
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    mode = [[], [[0], [1], [2], [3]], [[0, 2], [1, 3]], [[0, 1], [1, 2], [2, 3], [3, 0]], [[3, 0, 1], [0, 1, 2], [1, 2, 3], [2, 3, 0]], [[0, 1, 2, 3]]]
    dfs(graph, 0)
    print(minArea)