https://www.acmicpc.net/problem/17142
17142번: 연구소 3
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고
www.acmicpc.net
#문제
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.
연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.
* 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 *시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.
0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
* - 3 2 3 4 *연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.
#알고리즘
브루트포스 알고리즘
그래프 이론
그래프 탐색
너비 우선 탐색
#난이도
Gold 4
#풀이방법
사실 너비 우선 탐색 문제는 많이 풀어봤기에 문제 자체를 구현하는 것에는 어려움이 없었다. 그러나 이 문제에서는 까다로운 조건들이 조금(?) 추가돼서 그 조건들을 맞추면서 구현하는 것에 많은 어려움이 있었다.
조건 1. 비활성 바이러스 중 조합을 이용하여 M개의 활성 바이러스를 활성화 시키는 것
조건 2. 활성 바이러스 ,비활성 바이러스 , 벽, 빈 공간등 기존에 랭킹이 낮은 문제들보다 구분해야할 등장요소들이 많은 것
나 같은 경우는 기존 유형에 문제에 익숙해져서 그런지 조합을 사용해서 비활성 바이러스를 활성화 시키는 것이 아닌
백트래킹으로 이를 구현하려고 하다보니 원하는데로 바이러스가 활성이 되지 않아 많은 어려움을 겪었다.
간신히 조합 코드를 구글링하여 비활성 바이러스를 활성했다....
기존에 내 방식을 추구하는 것이 아닌 문제의 요구조건에 따라 유도리 있게 코드를 짜야하는 것임을 다시 한번 상기시켰다.
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 | } public static void combination(boolean[] visited, int start, int n, int r) { if (r == 0) { Virus[] active_v = new Virus[M]; int idx = 0; for(int i=0; i<v_list.size(); i++) { if(visited[i]) { active_v[idx++] = v_list.get(i); }//방문처리된 배열 요소를 활성화된 v_list에 넣어줌 } //활성된 바이러스를 너비우선으로 탐색한다. back_track(active_v); return; } for (int i = start; i < n; i++) { visited[i] = true; combination(visited, i + 1, n, r - 1); visited[i] = false; } }//백트래킹을 사용한 조합 코드 | cs |
그 후 활성화된 바이러스를 queue에 넣은 후, 벽과 활성화된 바이러스를 방문처리 한다. 빈 벽을 카운트 한후 시뮬레이션을 돌려 빈벽이 0인 경우, min 최소값을 비교한후 브루트포스 알고리즘으로 모두 다 비교한다.
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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | public static void back_track(Virus[] v) { Queue<Virus> queue = new LinkedList<>(); boolean[][] visited = new boolean[N][N]; int empty = 0; for(int i=0; i<v.length; i++) { queue.add(v[i]); visited[v[i].y][v[i].x] = true; }//활성화된 바이러스를 queue에 추가 for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { if(map[i][j] == 1) { visited[i][j] = true; }//벽일 경우 방문처리 else if(map[i][j] == 0) { empty++; }//빈벽이면 추가시켜줌 } }//벽은 방문처리 if(empty == 0) { min = 0; return; }//빈벽이 아예 없다면 시간은 0초 while(!queue.isEmpty()){ Virus vir = queue.poll(); for(int i=0; i<4; i++) { if(0 > vir.y+dy[i] || N <= vir.y+dy[i] || 0 > vir.x+dx[i] || N <= vir.x+dx[i]) continue; //범위에서 벗어나거나 if(visited[vir.y+dy[i]][vir.x+dx[i]]) continue; //이미 방문한 경우, continue 처리 queue.add(new Virus(vir.y+dy[i],vir.x+dx[i],vir.count+1)); visited[vir.y+dy[i]][vir.x+dx[i]] = true; //방문 처리 if(map[vir.y+dy[i]][vir.x+dx[i]] == 0) empty--;//빈벽인 경우 하나씩 빼줌 if(empty == 0) { if(vir.count < min) min = vir.count+1; break; }//빈벽이 없는 경우 모두 감염된 것이니 최소값을 비교한후 끝낸다. } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); map = new int[N][N]; M = sc.nextInt(); for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { map[i][j] = sc.nextInt(); if(map[i][j] == 2) { v_num++; v_list.add(new Virus(i,j,0)); }//바이러스 리스트 } } boolean[] visited = new boolean[v_num]; combination(visited,0,v_num,M); if(min == Integer.MAX_VALUE) System.out.println(-1); else System.out.println(min); } | cs |
#전체 코드
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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 | import java.util.*; import java.io.*; //1t class Main { static int[] dy = {1,0,-1,0}; static int[] dx = {0,1,0,-1}; static int N,M; static int[][] map; static int v_num; static ArrayList<Virus> v_list = new ArrayList<>(); static int min = Integer.MAX_VALUE; public static void back_track(Virus[] v) { Queue<Virus> queue = new LinkedList<>(); boolean[][] visited = new boolean[N][N]; int empty = 0; for(int i=0; i<v.length; i++) { queue.add(v[i]); visited[v[i].y][v[i].x] = true; }//활성화된 바이러스를 queue에 추가 for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { if(map[i][j] == 1) { visited[i][j] = true; }//벽일 경우 방문처리 else if(map[i][j] == 0) { empty++; }//빈벽이면 추가시켜줌 } }//벽은 방문처리 if(empty == 0) { min = 0; return; }//빈벽이 아예 없다면 시간은 0초 while(!queue.isEmpty()){ Virus vir = queue.poll(); for(int i=0; i<4; i++) { if(0 > vir.y+dy[i] || N <= vir.y+dy[i] || 0 > vir.x+dx[i] || N <= vir.x+dx[i]) continue; //범위에서 벗어나거나 if(visited[vir.y+dy[i]][vir.x+dx[i]]) continue; //이미 방문한 경우, continue 처리 queue.add(new Virus(vir.y+dy[i],vir.x+dx[i],vir.count+1)); visited[vir.y+dy[i]][vir.x+dx[i]] = true; //방문 처리 if(map[vir.y+dy[i]][vir.x+dx[i]] == 0) empty--;//빈벽인 경우 하나씩 빼줌 if(empty == 0) { if(vir.count < min) min = vir.count+1; break; }//빈벽이 없는 경우 모두 감염된 것이니 최소값을 비교한후 끝낸다. } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); map = new int[N][N]; M = sc.nextInt(); for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { map[i][j] = sc.nextInt(); if(map[i][j] == 2) { v_num++; v_list.add(new Virus(i,j,0)); }//바이러스 리스트 } } boolean[] visited = new boolean[v_num]; combination(visited,0,v_num,M); if(min == Integer.MAX_VALUE) System.out.println(-1); else System.out.println(min); } public static void combination(boolean[] visited, int start, int n, int r) { if (r == 0) { Virus[] active_v = new Virus[M]; int idx = 0; for(int i=0; i<v_list.size(); i++) { if(visited[i]) { active_v[idx++] = v_list.get(i); }//방문처리된 배열 요소를 활성화된 v_list에 넣어줌 } //활성된 바이러스를 너비우선으로 탐색한다. back_track(active_v); return; } for (int i = start; i < n; i++) { visited[i] = true; combination(visited, i + 1, n, r - 1); visited[i] = false; } }//백트래킹을 사용한 조합 코드 } class Virus{ int y,x,count; Virus(int y,int x,int count){ this.y = y; this.x= x; this.count = count; } } | cs |
'알고리즘 문제' 카테고리의 다른 글
| 백준 17406번) 배열 돌리기 4 (JAVA) (0) | 2022.08.11 |
|---|---|
| 백준 16637번) 괄호 추가하기(JAVA) (0) | 2022.08.10 |
| 프로그래머스) 튜플 (0) | 2022.08.02 |
| 백준 2529번) 부등호 (JAVA) (0) | 2022.07.25 |
| 백준 6236번) 용돈 관리 (JAVA) (0) | 2022.07.21 |