글 읽기 - 연구소3 문제 뭐가 문제인 걸까요?

qls0860 4년 전 0

빈 곳이든 바이러스든, 똑같이 시간 증가시켜서 2차원 배열에 저장해놓고

증가시킨 시간을 빈 곳일때만 답으로 취하게 했는데

96%쯤에 틀리네요.

package Main2;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N, M, m[][], tmp[][], my[] = {-1,0,1,0}, mx[] = {0,1,0,-1}, MAX = 987654321, CNT;
	static ArrayList<int[]> virus = new ArrayList<>();
	static Queue<int[]> q = new LinkedList<>();
	
	static int min(int depth, int s, Stack<int[]> active) throws Exception {
		if (depth == M) { // m개를 골랐을 때 (조합)
			int ret = MAX, i, j;
			
            // 고른 바이러스를 활성화 시킴
			for (i = 0; i < active.size(); i++) {
				int[] v = active.elementAt(i);
				q.add(v);
				m[v[0]][v[1]] = -1; 
			}
			
            // bfs로 퍼뜨리기
			while (!q.isEmpty()) {
				int[] cur = q.poll();
				
				for (int dir = 0; dir < 4; dir++) {
					int ny = cur[0] + my[dir], nx = cur[1] + mx[dir];
					// 범위 벗어나거나, 방문했거나, 벽인 경우 건너뛰기
					if (ny < 0 || ny >= N || nx < 0 || nx >= N || m[ny][nx] < 0 || m[ny][nx] == 1) continue;
					
                    // 시간
					int time = m[cur[0]][cur[1]] - 1;

                    // 빈 칸일때만 값 초기화
					if (m[ny][nx] == 0) ret = time;
					
					m[ny][nx] = time;
					
					q.add(new int[] {ny, nx});
				}
			}

			boolean flag = true;
			
			for (i = 0; i < N; i++) {
				for (j = 0; j < N; j++) {
					if (m[i][j] == 0) 
						flag = false; // 빈칸이 남아있을 경우 실패
					
					m[i][j] = tmp[i][j];
				}
			}
			
			return flag ? (-ret - 1) : MAX;
		}
		
		int i, ret = MAX;
		
		for (i = s; i < CNT; i++) {
			active.add(virus.get(i));
			ret = Math.min(ret, min(depth + 1, i + 1, active));
			active.pop();
		}
		
		return ret;
	}
	
	public static void main(String[] args) throws Exception {
		String[] s = br.readLine().split(" ");
		N = Integer.parseInt(s[0]);
		M = Integer.parseInt(s[1]);
		
		m = new int[N][N];
		tmp = new int[N][N];
		
		int i, j;
		
		for (i = 0; i < N; i++) {
			s = br.readLine().split(" ");
			for (j = 0; j < N; j++) {
				m[i][j] = Integer.parseInt(s[j]);
				tmp[i][j] = m[i][j];
				
				if (m[i][j] == 2) virus.add(new int[] {i, j});
			}
		}
		
		CNT = virus.size();
		
		int ans = min(0, 0, new Stack<>());
		
		bw.write((ans == MAX ? -1 : ans) + "");
		bw.close();
	}
}

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

문제

문제

출처

ICPC

연구소3 문제 뭐가 문제인 걸까요?

qls0860 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말