백준 #14502 - 연구소 : 구현, 그래프 탐색

(python3)

구현 아이디어

각 기능을 구현한 함수명을 함께 작성했습니다.

1. 벽 3개를 세울 수 있는 모든 방법을 찾아야 합니다.

• next() 는 바로 다음 빈칸을 찾습니다.
• next_wall() 에서는 다음 벽 3개 조합을 찾습니다. 3번 벽을 한칸 다음으로 옮겨보고, 옮길 공간이 없으면 그 2번 벽을 한칸 다음으로, 3번 벽은 2번 벽 바로 다음으로 배치합니다. 이때 3번 벽이 또 갈 곳이 없다면 1번 벽을 한칸 다음으로 옮기고 그 다음에 2번, 그 다음에 3번 벽을 배치합니다. 이때 3번 벽을 배치할 공간이 없으면 모든 벽의 조합을 다 확인해본 꼴이 됩니다.

2. 벽을 세우고, 맨 처음 배치되어 있는 모든 바이러스에 대해 dfs 를 수행하여 바이러스가 다 퍼진 뒤의 상태를 확인합니다. (infection())

• 바이러스가 퍼질 수 있는 모든 공간을 다 찾을 것이기 때문에 탐색법에 따른 시간복잡도 차이가 거의 없으니 구현이 쉬운 dfs 를 채택했습니다.
• 새롭게 퍼져나간 바이러스는 3으로 체크해서 모든 2 (바이러스 최초 위치) 만 dfs 의 시작점으로 활용하였습니다. (next_virus())

3. 바이러스가 다 퍼진 뒤에 남아있는 0칸의 개수를 세어줍니다. (count_safe_zone())

이를 반복해서 남은 0칸 개수의 maximum 값을 계속 갱신해나갑니다.

구현 코드

import copy
def solution(input) : 
	# 맵 세로, 가로 크기 입력 받기
    R,C = list(map(int,input().split()))
    # 맵 정보 입력 받기
    MAP = []
    for _ in range(R) :
        MAP.append(list(map(int, input().split())))
    # 다음 0 찾기
    def next(w) :
        r,c = w
        for nr in range(r,R) :
            if nr == r :
                start = c+1
            else : start = 0
            for nc in range(start,C) :
                if MAP[nr][nc] == 0 :
                    return (nr,nc)
        return -1
	# 3개 벽 다음 조합 찾기
    def next_wall() :
        wall[2] = next(wall[2])
        if wall[2] == -1 :
            wall[1] = next(wall[1])
            wall[2] = next(wall[1])
            if wall[2] == -1 :
                wall[0] = next(wall[0])
                wall[1] = next(wall[0])
                wall[2] = next(wall[1])
                if wall[2] == -1 :
                    return -1
    # 다음 바이러스 찾기
    def next_virus(w) :
        r,c = w
        for nr in range(r,R) :
            if nr == r :
                start = c+1
            else : start = 0
            for nc in range(start,C) :
                if MAP[nr][nc] == 2 :
                    return (nr,nc)
        return -1
    # 모든 초기 바이러스에 대해 dfs, 감염 이후 맵 만들기
    def infection(map) :
        def dfs(map, v) :
            vr,vc = v
            map[v[0]][v[1]] = 3
            dir = [(1,0),(-1,0),(0,1),(0,-1)]
            for dr, dc in dir :
                if vr+dr >= 0 and vr+dr < R and vc+dc >= 0 and vc+dc < C :
                    if map[vr+dr][vc+dc] == 0 :
                        nv = (vr+dr, vc+dc)
                        dfs(map,nv)
        
        v = next_virus((0,-1))
        while v != -1 :
            dfs(map,v)
            v = next_virus(v)
    # 감염 이후 맵의 safe zone 개수 세기
    def count_safe_zone(map) :
        cnt = 0
        for r in range(R) :
            for c in range(C) :
                if map[r][c] == 0 :
                    cnt+=1
        return cnt
    # 기존 맵에 벽을 세우고, 감염 시뮬레이션 이후 빈칸 개수 찾기
    def calculate_safe_zone() :
        nmap = copy.deepcopy(MAP)
        for wr, wc in wall :
            nmap[wr][wc] = 1
        infection(nmap)
        cnt = count_safe_zone(nmap)
        return cnt
        
    # 가능한 모든 벽 조합에 대해 시뮬레이션 시행하고 max 값 갱신해나가기
    wall = [next((0,-1)), next(next((0,-1))), next(next((0,-1)))]

    cnt = 0
    while next_wall() != -1 :
        ncnt = calculate_safe_zone()
        cnt = max(cnt, ncnt)
    
    print(cnt)

solution(input)