문제
접근 방법을 생각해보자.
방법 1: 생각나는 것: ~47분
바이러스 위치 확인하기
빈칸 위치 확인하기
빈칸 nC3 으로 위치뽑기
- 바이러스 위치 기준으로 돌면서 dfs로 맵 채우기
- 전체 - 바이러스 - 벽수로 빈값 구하기
- 빈값 크기 비교 하기
(n * m)C3 * (n * m) => 약 266만
구현
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
directions = [ [0,1], [0,-1], [1,0], [-1, 0] ] def dfs(x,y, visited): global n,m, lab_map; for i in range(4): nx = x + directions[i][0] ny = y + directions[i][1] if nx < 0 or ny < 0 or nx >= n or ny >= m: continue if lab_map[nx][ny] != 0: continue if visited[nx][ny] != 0: continue visited[nx][ny] = 1 dfs(nx,ny,visited) virus_location_list = [] empty_location_list = [] wall_count = 0 for i in range(n): for j in range(m): if lab_map[i][j] == 2: virus_location_list.append([i,j]) elif lab_map[i][j] == 1: wall_count += 1 elif lab_map[i][j] == 0: empty_location_list.append([i,j]) max_count = 0 len_empty_location_list = len(empty_location_list) for i in range(len_empty_location_list): ix,iy = empty_location_list[i] lab_map[ix][iy] = 1 for j in range(i + 1, len_empty_location_list): jx,jy = empty_location_list[j] lab_map[jx][jy] = 1 for k in range(j + 1, len_empty_location_list): kx,ky = empty_location_list[k] lab_map[kx][ky] = 1 visited = [[0] * m for _ in range(n)] for [x,y] in virus_location_list: visited[x][y] = 1 dfs(x,y,visited) count_zero = 0 for x in range(n): for y in range(m): if visited[x][y] == 0: count_zero += 1 max_count = max(max_count, count_zero - 3 - wall_count) lab_map[kx][ky] = 0 lab_map[jx][jy] = 0 lab_map[ix][iy] = 0 print(max_count)
더 깔끔한 코드
알게된 것
- 200만대면 2초안에 풀린다.