[python] BOJ 14502 연구소

BOJ 14502 연구소

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

14502번: 연구소

 

자세한 문제 설명은 위의 링크를 참조하세요.

 

 

아이패드를 한번 활용해보려고.. 써봤는데 글씨가 너무 악필이라 가독성이 떨어지네요 ㅠㅠ

그래도 쓴게 아까워서 올려봅니다...

 

 

import copy from itertools import combinations from collections import deque def solve():     global answer     # 새롭게 세울 벽 3개의 모든 조합 얻기     for com in combinations(empty, wall_num):         graph_tmp = copy.deepcopy(graph)         #조합으로 3개 좌표 뽑은거 벽세우기         for x_w, y_w in com:             graph_tmp[x_w][y_w] = 1         # 바이러스 위치 찾아서 큐에 넣기         queue = deque()         for i in range(N):             for j in range(M):                 if graph[i][j] == 2:                     queue.append((i,j))               # 바이러스마다 전파 끝날 때까지 반복         while queue:             x,y = queue.popleft()             for i in range(4):                 nx = x + dx[i]                 ny = y + dy[i]                 #범위 체크                 if nx <0 or nx >=N or ny <0 or ny>=M:                     continue                 #벽 체크                 if graph_tmp[nx][ny] == 1:                     continue                 if graph_tmp[nx][ny] == 0:                     graph_tmp[nx][ny] = 2                     queue.append((nx,ny))         # 안전영역 카운트         cnt = 0         for row in graph_tmp:             cnt += row.count(0)         # max로 갱신         # print(cnt)             answer = max(answer,cnt) if __name__ == "__main__":     N, M = map(int, input().split())     graph = []     for i in range(N):         tmp = list(map(int, input().split()))         graph.append(tmp)     wall_num = 3     # 벽을 세울 수 있는 빈 공간 정보를 리스트에 저장     empty = []     for i in range(N):         for j in range(M):             if graph[i][j] == 0:                 empty.append((i,j))     dx = [-1,1,0,0]     dy = [0, 0, -1,1]     answer = 0     solve()     print(answer)