[Python] 14502번 : 연구소

 

문제 3줄 요약

1. 0은 빈칸, 1은 벽, 2는 바이러스

2. 벽이 세워지지 않는 빈칸에는 바이러스가 퍼진다.

3. 3개의 벽을 세워 바이러스 퍼지는 것을 최소화해라!

 

 

 

3개의 벽을 세울 수 있는 모든 경우의 수를

브루트포스 알고리즘을 이용하고

벽을 임의로 세우고 난 후, 바이러스를 BFS로 확산시켜

남아 있는 빈칸의 수를 최대가 나올 때까지 갱신시킨다.

 

from sys import stdin

# 좌표 넣을 구조체
class XY:
    def __init__(self, x, y):
        self.x = x
        self.y = y

# 바이러스 확산
def BFS(copy_list, two):
    Q = []
    for check in two:
        Q.append(check)

	## 상하좌우로 확산
        while(len(Q) != 0):                    
            ## RIGHT
            if (Q[0].y < M-1):
                if copy_list[Q[0].x][Q[0].y+1] == 0:
                    copy_list[Q[0].x][Q[0].y+1] = 2
                    Q.append(XY(Q[0].x,Q[0].y+1))        

            ## DOWN
            if (Q[0].x < N-1):
                if copy_list[Q[0].x+1][Q[0].y] == 0:
                    copy_list[Q[0].x+1][Q[0].y] = 2
                    Q.append(XY(Q[0].x+1,Q[0].y))

            ## LEFT
            if (Q[0].y > 0):
                if copy_list[Q[0].x][Q[0].y-1] == 0:
                    copy_list[Q[0].x][Q[0].y-1] = 2
                    Q.append(XY(Q[0].x,Q[0].y-1))          
            
            ## UP
            if (Q[0].x > 0):
                if copy_list[Q[0].x-1][Q[0].y] == 0:
                    copy_list[Q[0].x-1][Q[0].y] = 2
                    Q.append(XY(Q[0].x-1,Q[0].y))
            
            del Q[0]

    result = 0
    for c_item in copy_list:
        result += c_item.count(0)   
    return result


if __name__ == "__main__":
## 지도의 세로 크기 N, 가로 크기 M
    N, M = map(int, stdin.readline().split())
    map_list = []
    two_list = []
    answer = 0

    for x in range(N):
    ## N개의 지도의 모양
        numbers = list(map(int, stdin.readline().split()))
        line = []
        for y, num in enumerate(numbers):
            if num == 2:
                two_list.append(XY(x,y))
            line.append(num)
        map_list.append(line)

## 첫 번째 벽 경우의 수
    for first in range(N*M):
        if map_list[first//M][first%M] == 0:
            map_list[first//M][first%M] = 1
	## 두 번째 벽 경우의 수
            for sec in range(first+1, N*M):
                if map_list[sec//M][sec%M] == 0:
                    map_list[sec//M][sec%M] = 1
		## 세 번째 벽 경우의수
                    for trd in range(sec+1, N*M):
                        if map_list[trd//M][trd%M] == 0:
                            map_list[trd//M][trd%M] = 1

                            copy_list = [maps.copy() for maps in map_list]
                            cnt = BFS(copy_list, two_list)
                            answer = answer if answer > cnt else cnt
                            map_list[trd//M][trd%M] = 0
                    
                    map_list[sec//M][sec%M] = 0
            map_list[first//M][first%M] = 0

## 최대 빈칸의 수
    print(answer)

 

BFS가 익숙하지 않아 코드를 작성하는데 시간이 오래걸렸다.

좀 더 많은 BFS, DFS 알고리즘 문제를 풀어보고

구현 시간을 줄여보도록 노력해야겠다.

 

끝!