(22 복습) 삼성 SW 역량 테스트 기출 문제 / 백준 / 14502번: 연구소

[sallyy1]

# 벽을 3개씩 세울 수 있음 -> 모든 경우에 대해 탐색 (브루트포스)
# 0: 빈칸     1: 벽    2: 바이러스

from collections import deque

r, c = map(int, input().split())
a = [ list(map(int, input().split())) for _ in range(r)]



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

answer = 0 # 안전 영역 크기의 최댓값

def bfs(a, r, c):
    #### (실패) b = a[:][:] # a 배열을 복사한 Copy 배열 -> 이렇게 하니까 a 배열도 b 배열 따라서 값이 바뀜
    b = [[0]*c for _ in range(r)]



    ## 1. queue 준비
    q = deque()

    for i in range(r):
        for j in range(c):
            b[i][j] = a[i][j] # 값 옮겨담기

            if a[i][j] == 2:
                q.append((i, j))


    ## 2. BFS 탐색
    while q:
        x, y = q.popleft()

        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]

            if 0<=nx<r and 0<=ny<c:
                if a[nx][ny] == 1:
                    continue

                if b[nx][ny] == 0: # 벽 or 또다른 바이러스라면, 바이러스가 퍼지지 못하고 패스
                    b[nx][ny] = 2 # 바이러스 퍼짐
                    q.append((nx, ny)) # 방문할 큐에 추가 (주의 !!)


    ## 3. 해당 턴의 안전 영역의 크기 계산
    cnt = 0

    for i in range(r):
        for j in range(c):
            if b[i][j] == 0: # (주의)
                cnt += 1

    # print('####')
    # for line in a:
    #     print(line)
    # print()
    #
    # for line in b:
    #     print(line)
    # print()

    return cnt



for r1 in range(r):
    for c1 in range(c):
        if a[r1][c1] != 0:
            continue

        for r2 in range(r):
            for c2 in range(c):
                if a[r2][c2] != 0:
                    continue

                for r3 in range(r):
                    for c3 in range(c):
                        if a[r3][c3] != 0:
                            continue

                        # 3개의 위치가 모두 다를 때에만 수행할 수 있도록
                        if r1 == r2 and c1 == c2:
                            continue
                        if r2 == r3 and c2 == c3:
                            continue
                        if r1 == r3 and c1 == c3:
                            continue

                        ## <벽 세우기>
                        a[r1][c1] = 1
                        a[r2][c2] = 1
                        a[r3][c3] = 1


                        # print()
                        # print('시작')
                        # for line in a:
                        #     print(line)
                        # print()


                        result_cnt = bfs(a, r, c)
                        if answer < result_cnt:
                            answer = result_cnt

                        ## <벽 지우기>
                        a[r1][c1] = 0
                        a[r2][c2] = 0
                        a[r3][c3] = 0

print(answer)