글 읽기 - 15683 반례를 찾아주시면 감사하겠습니다!

park345601 4년 전 0

게시판에 있는 반례 모음집부터 모든 게시글의 반례를 돌려본 것 같은데 다 정답이 출력됩니다.

그런데 제출하면 7%였나? 계속 틀렸습니다가 나옵니다.

작은 케이스로 생각했던 예제입력들에 대해서는 모두 정상적으로 출력이 되는데 제가 생각하지 못한 반례가 있으면 알려주세요 ㅜㅜ

def count(table):
    global ans
    c = 0
    for i in range(n):
        for j in range(m):
            if table[i][j] == 0:
                c += 1
    ans = min(ans, c)

def fill(table, idx):
    # 리스트 cctv에 포함된 cctv를 idx로 현재 배치할 cctv를 선택

    # 모든 cctv에 대해서 감시 수행했으면 사각지대 계산
    if idx == len(cctv):
        count(table)
        return
    
    i, j, cctv_n = cctv[idx]
    os = oversight[cctv_n]
    # 한번에 볼 수 있는 집합들의 집합: os
    for o in os:
        t_table = []
        for t in table:
            t_table.append(t[:])
        
        # 한번에 볼수있는 모든 방향에 대해 적용
        for dx, dy in o:
            x, y = i, j
            while 0<=x+dx<n and 0<=y+dy<m:
                x += dx
                y += dy
                if t_table[x][y] == 6:
                    break
                if t_table[x][y] == 0:
                    # 감시한 공간(#)을 -1로 표시
                    t_table[x][y] = -1
        
        fill(t_table, idx+1)

n, m = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(n)]
cctv = []
tmp = list(range(1, 6))
# 감시할 수 있는 방향
# oversight[i] : i번 카메라가 한번에 볼 수 있는 집합들의 집합
# (dx, dy)
oversight = {1:[[(1, 0)], [(0, 1)], [(-1, 0)], [(0, -1)]],\
            2:[[(1, 0), (-1, 0)], [(0, 1), (0, -1)]],\
            3:[[(1, 0), (0, 1)], [(0, 1), (-1, 0)], [(-1, 0), (0, -1)], [(-1, 0), (0, 1)]],\
            4:[[(1, 0), (0, 1), (-1, 0)], [(0, 1), (-1, 0), (0, -1)], [(-1, 0), (0, -1), (1, 0)], [(0, -1), (1, 0), (0, 1)]],\
            5:[[(1, 0), (0, 1), (-1, 0), (0, -1)]]}

for i in range(n):
    for j in range(m):
        if table[i][j] in tmp:
            cctv.append((i, j, table[i][j])) # 위치 + cctv번호(1~5)

ans = 100
fill(table, 0)
print(ans)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

15683 반례를 찾아주시면 감사하겠습니다!

park345601 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말