- 소요시간 : 1시간 40분
- 문제 사이트 : 백준
- 문제 수준 : 골드 3
- 문제 유형 : 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색
- 다른 사람의 풀이를 참고 했는가 ? : X
- 한 번 풀었다가 다시 푸는 문제인가 ? : X
- 문제 링크 : https://www.acmicpc.net/problem/17142
- 푼 날짜 : 2023.03.20
1. 사용한 자료구조 & 알고리즘
브루트포스 알고리즘을 적용하기 위한 DFS,
그리고 BFS 를 사용했다.
2. 사고과정
우선 연구소 1,2와 굉장히 비슷해서 전체적인 코드는 금방짰다. 120줄 정도인데 20분 안에 짠 것 같다. 그런데 제출하고 나니 80%쯤에서 틀렸다고 나왔다. 반례를 찾는데만 1시간 20분을 썼다. 사람들이 각각 막힌 반례들이 다르겠지만 내 반례는 이거였다.
" 그래프 탐색이 벽이 아닌 경우 계속 이루어진다. 그리고 BFS 를 한 후 map 에서의 count 의 최댓값을 찾는다. 그런데, 만약 이미 모든 빈칸 ( 0 ) 으로의 BFS 가 이루졌음에도 불구하고 비활성화된 바이러스 후보군으로의 BFS 가 계속해서 된다면, count 값이 더 증가되어서 나온다 " 였다.
그렇기에 BFS를 할 때 이전의 노드가 빈칸이었다면, count 값을 갱신하고, 비활성화된 바이러스라면 count 값을 갱신하지 않음으로써 문제를 해결할 수 있었다.
3. 풀이과정
- 바이러스 후보군을 ArrayList 담는다.
- 조합을 뽑는다. 깊이가 M 이 된다면 SpreadVirus 메소드를 실행
- map에서의 작업이 이루어지면 안되므로 map을 copy한 copyMap 을 만든다.
- copyMap[i][j]가 활성화 바이러스라면 큐에 담는다.
- BFS 를 하되, 이전의 노드가 빈칸(0) 이었다면 count 최대값을 갱신. 비활성화 바이러스(2) 였다면 최대값을 갱신 X
- check 메소드로 맵에 0이 하나라도 있나 확인한다. 0이 있다면 최솟값을 갱신하지 않는다. 0이 없다면 최솟값을 갱신.
4. 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int map[][];
static ArrayList<Integer[]> list=new ArrayList<>();
static boolean visited[];
static int M=0;
static int yy[]= {-1,1,0,0};
static int xx[]= {0,0,-1,1};
static int minVal=Integer.MAX_VALUE;
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st=new StringTokenizer(br.readLine());
int N=Integer.parseInt(st.nextToken());
M=Integer.parseInt(st.nextToken());
map=new int[N][N];
for(int i=0;i<N;i++) {
st=new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
int num=Integer.parseInt(st.nextToken());
if(num==2)
list.add(new Integer[] {i,j});
map[i][j]=num;
}
}
visited=new boolean[list.size()];
dfs(0,0);
if(minVal==Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(minVal);
}
public static void dfs(int depth,int start) {
if(depth==M) {
spreadVirus();
return ;
}
for(int i=start;i<visited.length;i++) {
if(!visited[i]) {
visited[i]=true;
Integer temp[]=list.get(i);
int y=temp[0];
int x=temp[1];
map[y][x]=3;
dfs(depth+1,i+1);
map[y][x]=2;
visited[i]=false;
}
}
}
public static void spreadVirus() {
Queue<Integer[]> queue =new LinkedList<>();
int copyMap[][]=new int[map.length][map.length];
boolean thisVisited[][]=new boolean[map.length][map.length];
for(int i=0;i<copyMap.length;i++)
copyMap[i]=map[i].clone();
for(int i=0;i<copyMap.length;i++) {
for(int j=0;j<copyMap.length;j++) {
if(copyMap[i][j]== 3) {
queue.add(new Integer[] {i,j,0,1});
thisVisited[i][j]=true;
}
}
}
int max=0;
while(!queue.isEmpty()) {
Integer temp[]=queue.poll();
int prevY=temp[0];
int prevX=temp[1];
int count=temp[2];
int mode=temp[3];
if(mode==1)
max=Math.max(count,max);
for(int i=0;i<4;i++) {
int nextY=prevY+yy[i];
int nextX=prevX+xx[i];
if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length)
continue;
if(copyMap[nextY][nextX]==1||thisVisited[nextY][nextX]==true)
continue;
thisVisited[nextY][nextX] = true;
if(copyMap[nextY][nextX]==0)
queue.add(new Integer[] {nextY,nextX,count+1,1});
else
queue.add(new Integer[] {nextY,nextX,count+1,0});
copyMap[nextY][nextX]= 3;
}
}
if(check(copyMap)) {
minVal=Math.min(minVal,max);
}
}
public static boolean check(int copyMap[][]) {
for(int i=0;i<copyMap.length;i++) {
for(int j=0;j<copyMap.length;j++) {
if(copyMap[i][j]==0) return false;
}
}
return true;
}
}5. 결과
24일 전에도 시도했었던 문제다. 그때도 못풀었는데
오늘에서야 반례를 알아내고 문제를 푸니
속이 그냥 뻥 ~ ~ ~ ~
6. 회고
처음에는 문제의 억까라고 생각했었다. 계속 안되니까 문제에서의 예시가 잘못된 것이라고 생각했다. 정보를 충분히 제공하지 않았다고 말이다.
벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
라는 문구도 분명히 써있다. 문제는 잘못이 없다. 문제를 꼼꼼하게 읽자.
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212
