구현은 빡시다. (#15683 감시)

#15683 감시 https://www.acmicpc.net/problem/15683

15683번: 감시

 

구현할 내용이 너무 많아서 버거웠다.

하지만 모르겠던 부분은 하나도 없었다.

 

카메라별로 4개의 방향을 가지기 때문에, (카메라 수)^4 개의 경우의 수가 나온다.

이 경우의 수를 dfs 등의 방법을 통해 전부 구한 다음에

각각의 상황에 맞게 조건문을 작성하여 동작하게 하면 된다.

 

from copy import deepcopy

h, w = map(int, input().split())


maps = []
cctvs = []  # [y,x] 꼴로 카메라의 위치가 들어간다.
# cctv : 1( >), 2(< >), 3(^ >), 4(<^>), 5(상하좌우)
# 6은 벽
for y in range(h):
    tmp = [int(x) for x in input().split()]
    for x in range(w):
        if 1 <= tmp[x] <= 5:
            cctvs.append([y, x])
    maps.append(tmp)

# for m in maps:
#     print(m)

# print(cctvs)


# 카메라를 배치하는 경우의 수를 전부 구하기
results = []


def dfs(l):
    if len(l) == len(cctvs):
        results.append(l)
        return
    for i in range(4):
        dfs(l + [i])


dfs([])


def show_top(maps, y, x):
    for i in range(y - 1, -1, -1):
        if maps[i][x] == 6:
            break
        elif maps[i][x] == 0:
            maps[i][x] = "#"


def show_left(maps, y, x):
    for i in range(x - 1, -1, -1):
        if maps[y][i] == 6:
            break
        elif maps[y][i] == 0:
            maps[y][i] = "#"


def show_down(maps, y, x):
    for i in range(y + 1, h):
        if maps[i][x] == 6:
            break
        elif maps[i][x] == 0:
            maps[i][x] = "#"


def show_right(maps, y, x):
    for i in range(x + 1, w):
        if maps[y][i] == 6:
            break
        elif maps[y][i] == 0:
            maps[y][i] = "#"


answer = h * w

for t in results:

    temp_map = deepcopy(maps)
    for i in range(len(cctvs)):

        y, x = cctvs[i]
        cctv = maps[y][x]
        direction = t[i]

        if cctv == 1:
            if direction == 0:  # 위
                show_top(temp_map, y, x)
            elif direction == 1:  # 왼쪽
                show_left(temp_map, y, x)
            elif direction == 2:  # 아래
                show_down(temp_map, y, x)
            elif direction == 3:
                show_right(temp_map, y, x)
        elif cctv == 2:
            if direction == 0 or direction == 2:  # 위, 아래는 동시에 본다.
                show_top(temp_map, y, x)
                show_down(temp_map, y, x)
            elif direction == 1 or direction == 3:  # 좌, 우는 동시에 본다.
                show_left(temp_map, y, x)
                show_right(temp_map, y, x)
        elif cctv == 3:
            if direction == 0:
                show_top(temp_map, y, x)
                show_right(temp_map, y, x)
            elif direction == 1:
                show_left(temp_map, y, x)
                show_top(temp_map, y, x)
            elif direction == 2:
                show_left(temp_map, y, x)
                show_down(temp_map, y, x)
            elif direction == 3:
                show_right(temp_map, y, x)
                show_down(temp_map, y, x)
        elif cctv == 4:
            if direction == 0:
                show_left(temp_map, y, x)
                show_top(temp_map, y, x)
                show_right(temp_map, y, x)
            elif direction == 1:
                show_top(temp_map, y, x)
                show_left(temp_map, y, x)
                show_down(temp_map, y, x)
            elif direction == 2:
                show_left(temp_map, y, x)
                show_down(temp_map, y, x)
                show_right(temp_map, y, x)
            elif direction == 3:
                show_top(temp_map, y, x)
                show_right(temp_map, y, x)
                show_down(temp_map, y, x)
        elif cctv == 5:
            show_top(temp_map, y, x)
            show_left(temp_map, y, x)
            show_right(temp_map, y, x)
            show_down(temp_map, y, x)

    # for m in maps:
    #     print(m)
    tmp = 0
    for row in temp_map:
        for v in row:
            if v == 0:
                tmp += 1
    answer = min(answer, tmp)
print(answer)

 

 

정답이긴 했으나 속도가 굉장히 느렸다.

 

약간의 개선을 더한다면

 

move 함수를 하나로 통일할 수 있을 것 같다. (고민이 좀 필요할 것 같긴 하다.)

그리고, 5번 카메라의 경우에는 사방을 다 비추기 때문에 경우의 수는 1이다.

이 경우를 제외하고 케이스를 만든다면 더욱 효율적인 코드가 되었을 것이다.