14502번: 연구소

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

 

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

import sys
from collections import defaultdict, deque
import itertools

N, M = map(int, sys.stdin.readline().split())

MAP = [[1 for _ in range(M+2)] for _ in range(N+2)]
virus = []
empty = []
wall = []
for n in range(1, N+1) :
    line = list(map(int, sys.stdin.readline().split()))
    for idx, l in enumerate(line) :
        if l == 2 : virus.append((n-1, idx))
        elif l == 0 : empty.append((n-1, idx))
        elif l == 1 : wall.append((n-1, idx))
    MAP[n][1:M+1] = line

# graph
graph = defaultdict(list)
for n in range(1, N+1) :
    for m in range(1, M+1) :
        if MAP[n][m] == 2 or MAP[n][m] == 0 :
            if MAP[n-1][m] == 0 : # 상
                graph[(n-1, m-1)].append((n-2, m-1))
            if MAP[n+1][m] == 0 : # 하
                graph[(n-1, m-1)].append((n, m-1))
            if MAP[n][m-1] == 0 : # 좌
                graph[(n-1, m-1)].append((n-1, m-2))
            if MAP[n][m+1] == 0 : # 우
                graph[(n-1, m-1)].append((n-1, m))

def BFS(start, graph, empty, wall, N, M) :
    coms = itertools.combinations(empty, 3)

    ans = 0
    for com in coms :
        q = deque(start)
        visited = [[0 for _ in range(M)] for _ in range(N)]
        for v in start :
            visited[v[0]][v[1]] = 1
        while q :
            u = q.popleft()

            for v in set(graph[u]) - (set(com) | set(wall)) :
                if visited[v[0]][v[1]] == 0 :
                    visited[v[0]][v[1]] = 1
                    q.append(v)

        zeros = 0
        for n in range(N) :
            for m in range(M) :
                if visited[n][m] + MAP[n+1][m+1] == 0 :
                    zeros += 1

        if ans < zeros :
            ans = zeros
    print(ans - 3)

BFS(virus, graph, empty, wall, N, M)

 

아이디어

1. 먼저 원래의 벽(1)을 제외하고 이동할 수 있는 graph를 생성한다.

# graph
graph = defaultdict(list)
for n in range(1, N+1) :
    for m in range(1, M+1) :
        if MAP[n][m] == 2 or MAP[n][m] == 0 :
            if MAP[n-1][m] == 0 : # 상
                graph[(n-1, m-1)].append((n-2, m-1))
            if MAP[n+1][m] == 0 : # 하
                graph[(n-1, m-1)].append((n, m-1))
            if MAP[n][m-1] == 0 : # 좌
                graph[(n-1, m-1)].append((n-1, m-2))
            if MAP[n][m+1] == 0 : # 우
                graph[(n-1, m-1)].append((n-1, m))

 

2. BFS

• 3개의 벽은 itertools의 combinations 메서드를 활용하여 nC3의 경우를 뽑는다.
• 각 경우마다 BFS를 실행한다. 노드를 탐색할 때, 노드가 벽과 새로 생길 벽에 해당하는 좌표라면 탐색하지 않는다.
• 방문 여부를 나타내는 리스트 visited와 MAP의 요소를 더해 감염되지 않은 0의 갯수를 센다.
• 새로운 벽 3개를 뺀 것을 답으로 구한다.

def BFS(start, graph, empty, wall, N, M) :
    coms = itertools.combinations(empty, 3)

    ans = 0
    for com in coms :
        q = deque(start)
        visited = [[0 for _ in range(M)] for _ in range(N)]
        for v in start :
            visited[v[0]][v[1]] = 1
        while q :
            u = q.popleft()

            for v in set(graph[u]) - (set(com) | set(wall)) :
                if visited[v[0]][v[1]] == 0 :
                    visited[v[0]][v[1]] = 1
                    q.append(v)

        zeros = 0
        for n in range(N) :
            for m in range(M) :
                if visited[n][m] + MAP[n+1][m+1] == 0 :
                    zeros += 1

        if ans < zeros :
            ans = zeros
    print(ans - 3)