BAEKJOON 14502

03 May 2020

문제

입력

---

나의 처음 코드

내가 문제를 푼 방식은 바로 백트래킹 + 브루트 포스로 해결하였다. 바이러스가 퍼지고 퍼지지 않은 공간의 최댓값을 구하면 된다. 그래서 빈칸의 좌표를 따로 저장한 후에, 벽을 세울 수 있는 모든 경우의 수를 for문으로 돌려준다. 벽이 3개가 추가된 맵을 바탕으로 bfs형식으로 풀면된다. 여기서 벽을 3개 추가하고 추가를 해제하는 방법에 대햇서 백트래킹 방법을 썼다. 코드는 다음과 같다.

N, M = list(map(int, input().split()))
wall_coord = []
virus_coord = []
map_list = []
#벽 좌표, 바이러스 좌표, 맵 입력 받기
for i in range(N):
    tmp_list = list(map(int, input().split()))
    for j in range(M):
        if tmp_list[j] == 0:
            wall_coord.append((i,j))
        if tmp_list[j] == 2:
            virus_coord.append((i,j))
    map_list.append(tmp_list)
        
max_space = -1
#오른 아래 왼 위
ud_list = [0, 1, 0, -1]
rl_list = [1, 0, -1, 0]

#브루트 포스 찾기
def solution(virus_list):
    cnt = 0
    visited_list = [[0] * M for _ in range(N)]
    while True:
        tmp_list = []
        for virus in virus_list:
            for i in range(4):
                new_x = virus[0] + ud_list[i]
                new_y = virus[1] + rl_list[i]
                if 0 <= new_x < N and 0 <= new_y < M and visited_list[new_x][new_y] == 0 and map_list[new_x][new_y] == 0:
                    cnt += 1
                    tmp_list.append((new_x, new_y))
                    visited_list[new_x][new_y] = 1
        virus_list = tmp_list
        if len(virus_list) == 0:
            #벽 3개를 세우고 solution들어왔으므로 -3 해줘야 한다
            return len(wall_coord) - 3 - cnt
     
     
#백트래킹 + 브루트포스 문제.                      
for i in range(len(wall_coord)-2):
    map_list[wall_coord[i][0]][wall_coord[i][1]] = 1
    for j in range(i+1,len(wall_coord)-1):
        map_list[wall_coord[j][0]][wall_coord[j][1]] = 1
        for k in range(j+1, len(wall_coord)):
            map_list[wall_coord[k][0]][wall_coord[k][1]] = 1
            #벽 세기
            ret_cnt = solution(virus_coord)
            max_space = ret_cnt if max_space < ret_cnt else max_space
            
            map_list[wall_coord[k][0]][wall_coord[k][1]] = 0
        map_list[wall_coord[j][0]][wall_coord[j][1]] = 0
    map_list[wall_coord[i][0]][wall_coord[i][1]] = 0
            

print(max_space)

코드를 짧게 만들고 싶었지만, 시간을 줄이기위해서 ,,,, ㅎㅎ