BrianaAI

안녕하세요.

브리아나입니다.

오늘은 백트래킹 말고,

시간 더 단축시킬 수 있는 경우를 풀어보겠습니다.

그래도 3개라는 숫자가 주어지니까 가능한 버전입니다.

문제.

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

풀이.

N, M = map(int, input().split())
arr = []
path = []
virus = []
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(M):
        if arr[i][j] == 0:
            path.append((i, j))
        elif arr[i][j] == 2:
            virus.append((i, j))

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def bfs(tlst):
    # [1] make wall 3 times
    for tx, ty in tlst:
        arr[tx][ty] = 1

    # [2] initialize virus info
    q = []
    w = [[0]*M for _ in range(N)]
    for vx, vy in virus:
        w[vx][vy] = 1
        q.append((vx, vy))
    chance = cnt-3

    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<M and w[nx][ny] == 0 and arr[nx][ny] == 0:
                w[nx][ny] = 1
                q.append((nx, ny))
                chance-=1

    # reset
    for tx, ty in tlst:
        arr[tx][ty] = 0

    return chance


cnt = len(path)
ans = 0

for i in range(cnt-2):
    for j in range(i+1, cnt-1):
        for k in range(j+1, cnt):
            ans = max(ans, bfs([path[i], path[j], path[k]]))
print(ans)

참고하세요 ~~