글 읽기 - 17142 연구소3 질문입니다.

dlrudrb1204 4년 전 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 *

위에 보는게 문제에 나와있는 예제입니다. 그런데 0,0을 보면 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다. 이렇게 문제에 있는게 이거에 안맞는 예제 아닌가요? 제가 문제를 잘못이해했는지 이게 자꾸 헷갈리네요,,,, 비활성상태라고 나와있으니깐 헷갈리네요,, 제가 생각하는것은 활성화상태가 되어야하는거 아닌가요?

제 소스코드에서는 75번줄에서 문제가 있는거같은데 저거때문에 헷갈리네요 ㅠㅠ 아직 이해가 안되서 그런지 100%까지 가는데 틀렸는데 아마 저거때문에 그런거같아서요 설명좀 부탁드릴게요~!

import java.io.*;
import java.util.Queue;
import java.util.LinkedList;
import java.awt.Point;
public class 연구소3_17142 {
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	
	static int map[][];
	static int copy[][];
	static boolean visit[];
	static boolean b_visit[][];
	
	static int ans;
	static int R;
	static int M;
	static Queue<Point> q_virus = new LinkedList<Point>();
	static LinkedList<Point> a_virus = new LinkedList<Point>();
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String in = br.readLine().trim();
		R = Integer.parseInt(in.split(" ")[0]);
		M = Integer.parseInt(in.split(" ")[1]);
		map = new int[R][R];
		copy = new int[R][R];
		
		
		
		b_visit = new boolean[R][R];
		q_virus = new LinkedList<Point>();
		
		for(int a=0;a<R;a++) {
			in = br.readLine().trim();
			for(int b=0;b<R;b++) {
				int temp = Integer.parseInt(in.split(" ")[b]);
				if(temp==0) continue;
				if(temp == 1) { //벽
					map[a][b]=-1;
					continue;
				}
				if(temp==2) {
					map[a][b]=-2;
					a_virus.add(new Point(a, b));
				}
				
			}
		}
		visit = new boolean[a_virus.size()];
		ans = Integer.MAX_VALUE;
		
		dfs(0,0);
		if(ans ==-1) {
			System.out.println(0);
		}
		else if(ans == Integer.MAX_VALUE) {
			System.out.println(-1);
		}
		else {
			System.out.println(ans);
		}
	}
	public static void bfs() {
		int temp_max=-1;
		while(!q_virus.isEmpty()) {
			Point p = q_virus.remove();
			int px = p.x;
			int py = p.y;
			b_visit[px][py]=true;
			for(int a=0;a<4;a++) {
				int rx = px+dx[a];
				int ry = py+dy[a];
				if(rx>=0 && ry>=0 && rx<R && ry<R) {
					if(b_visit[rx][ry]==false) {
						if(copy[rx][ry] > -1) {
							b_visit[rx][ry]=true;
							q_virus.add(new Point(rx, ry));
							copy[rx][ry]=copy[px][py]+1;
							temp_max = Math.max(temp_max, copy[rx][ry]);
						}
					}
				}
			}
		}
		if(check()) {
			ans = Math.min(ans, temp_max);
		}
	}
	public static boolean check() {
		for(int a=0;a<R;a++) {
			for(int b=0;b<R;b++) {
				if(copy[a][b]!=0) continue;
				if(b_visit[a][b]==false) {
					return false;
				}
			}
		}
		return true;
	}
	public static void dfs(int x, int level) {
		if(level == M) {
			copy();
			bfs();
			recover();
			return;
		}
		for(int a=x;a<a_virus.size();a++) {
			visit[a]=true;
			dfs(a+1,level+1);
			visit[a] = false;
		}
	}
	public static void recover() {
		for(int a=0;a<a_virus.size();a++) {
			if(visit[a]==false) continue;
			Point p = a_virus.get(a);
			map[p.x][p.y]=-2;
		}
	}
	public static void copy() {
		b_visit = new boolean[R][R];
		for(int a=0;a<a_virus.size();a++) {
			if(visit[a]==false) continue;
			Point p = a_virus.get(a);
			b_visit[p.x][p.y]= true;
			map[p.x][p.y]=0;
			q_virus.add(new Point(p.x, p.y));
		}
		for(int a=0;a<R;a++) {
			for(int b=0;b<R;b++) {
				copy[a][b] = map[a][b];
			}
		}
	}
}

rygns2418 4년 전 0

비활성을 활성으로 바꾸려고 의식적으로 처리해주기보단

그냥 비활성 바이러스가 있는곳은 퍼질수 있는곳으로 처리만 해주면 되던데용

dlrudrb1204 4년 전 0

4 2
0 1 1 0
2 1 1 2
2 1 1 2
0 1 1 0

위에 정답이 2라고 하던데 이거는 2이면

테스트 케이스 1번 예제인

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 *

이거도 답이 5가 되어야 하는거아닌가요? 아직 정확하게 이해가 안가네요,, 좀 문제를 파악할떄 정확하게 파악하는게 좋은거같은데 이 2가지 테스트 케이스에서 모순이 존재한다고 생각이들어서요 ㅠㅠㅠ 제가 잘못이해하고 있는건가요?

rygns2418 4년 전 0

4 2
0 1 1 0
2 1 1 2
2 1 1 2
0 1 1 0

의 경우

0초

0 1 1 0
* 1 1 *
2 1 1 2
0 1 1 0

1초

* 1 1 *
* 1 1 *
* 1 1 *
0 1 1 0

2초

* 1 1 *
* 1 1 *
* 1 1 *
* 1 1 *

모든 바이러스가 활성 상태이거나 그런게 아니고 그냥 빈자리만 없으면 되요

whddnr0218 4년 전 0

마지막 순간에 모든 자리에 바이러스가 있으면 끝입니다 활성상태라는 건 바이러스가 주변으로 퍼지는가 여부를 따지는 거구요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

17142 연구소3 질문입니다.

dlrudrb1204 4년 전 0

rygns2418 4년 전 0

dlrudrb1204 4년 전 0

rygns2418 4년 전 0

whddnr0218 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말