BrianaAI

안녕하세요.

브리아나입니다.

반례때문에 한참을 풀었네요..휴..(질문게시판 보고 알았습니다)

문제.

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

풀이.

N, M = map(int, input().split())
arr = []
virus = []
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(N):
        if arr[i][j] == 2: # 바이러스
            virus.append((i, j))
            arr[i][j] = 0 # 미리 바이러스 가능공간 0으로 없애버리기
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def solve(tlst):
    # make a wall
    w = [[0] * N for _ in range(N)]

    # [1] virus 넣어
    q = []
    for tx, ty in tlst:
        w[tx][ty] = 1
        q.append((tx, ty))

    m = 0
    while q:
        cx, cy = q.pop(0)
        for i in range(4):
            nx, ny = cx+dx[i], cy+dy[i]
            if 0<=nx<N and 0<=ny<N and w[nx][ny] == 0 and arr[nx][ny] == 0:
                w[nx][ny] = w[cx][cy]+1
                q.append((nx, ny))
                m = max(m, w[nx][ny])

    for i in range(N):
        for j in range(N):
            if w[i][j] == 0 and arr[i][j] == 0: # 그냥 길인데, 방문안한곳이 있다면
                return float("inf")
    # print("m: ", m-1, tlst)
    if m>0:
        return m-1
    return m


ans = float("inf")

def bfs(n, lst):
    global ans
    if len(lst) == M:
        ans = min(ans, solve(lst))
        return

    for i in range(n, len(virus)):
        if v[i] == 0:
            v[i] = 1
            bfs(i+1, lst+[virus[i]])
            v[i] = 0
    return

v = [0]*(len(virus))
bfs(0, [])

if ans == float("inf"):
    ans = -1
print(ans)

반례. 놓자마자 퍼짐. 그래서 저의 경우 0이 아닌 -1이 출력 되어서

5 2
1 1 1 1 1
1 1 2 1 1
1 1 2 1 1
1 1 1 1 1
1 1 1 1 1

if m>0:

return m-1

return m

이 문장을 넣어줬어요...휴...