성곽

1. 개요

• https://www.acmicpc.net/problem/2234

2. BFS + 완전탐색 풀이

import sys
from collections import deque

def solution():
    READLINE = lambda: sys.stdin.readline().rstrip()
    READINTS = lambda: list(map(int, READLINE().split()))
    
    M, N = READINTS()
    G = [READINTS() for _ in range(N)]
    D, DR, DC, UNDIFINED = 4, [0, -1, 0, 1], [-1, 0, 1, 0], -1
    
    SECTORS, SECTORTOT = [[-1]*M for _ in range(N)], []
    BLOCKED, Q = [], deque()

    maxIfCrashed = 0
    
    # bfs
    for n in range(N):
        for m in range(M):
            if SECTORS[n][m]!=UNDIFINED:
                continue

            SECTORS[n][m] = len(SECTORTOT)
            SECTORTOT.append(1)
            Q.append((n, m))

            while Q:
                i, j = Q.popleft()

                for d in range(4):
                    ni, nj = i+DR[d], j+DC[d]
                    
                    if G[i][j]&(1<<d):
                        if ni!=-1 and ni!=N and nj!=-1 and nj!=M:
                            BLOCKED.append((i, j, ni, nj))
                        continue

                    if SECTORS[ni][nj]!=UNDIFINED:
                        continue

                    SECTORS[ni][nj] = SECTORS[i][j]
                    SECTORTOT[-1]+=1
                    Q.append((ni, nj))

    # maxIfCrashed
    for ai, aj, bi, bj in BLOCKED:
        sectorA, sectorB = SECTORS[ai][aj], SECTORS[bi][bj]
        
        if sectorA==sectorB:
            continue

        aTot, bTot = SECTORTOT[sectorA], SECTORTOT[sectorB]
        maxIfCrashed = max(maxIfCrashed, aTot+bTot)

    print("\n".join([str(len(SECTORTOT)), str(max(SECTORTOT)), str(maxIfCrashed)]))

solution()