글 읽기 - 시간초과를 피할 수 있는 방법 여쭙습니다

thddudgns79 3년 전 0

조합을 통해 m개의 서로 다른 위치에 바이러스를 놓아보고, BFS로 바이러스 확산을 시뮬레이션했습니다.

여기서 어떻게 해야 시간초과를 피할 수 있을까요?

import java.util.*;

public class Main {
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static int n;
	static int m;
	static int[][] board;
	static ArrayList<Integer> virus;
	static boolean[] check;
	static int ans = 987654321;
	static int spaceToFilled = 0; 
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		board = new int[n][n];
		virus = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				board[i][j] = sc.nextInt();
				if (board[i][j] == 2)
					virus.add(i * n + j);
				if (board[i][j] == 0)
					spaceToFilled++;
			}
		}
		
		check = new boolean[virus.size()];
		dfs(0, 0);
		if (ans == 987654321)
			System.out.println(-1);
		else
			System.out.println(ans);

	}

	public static void dfs(int idx, int cnt) {
		if (cnt == m) {
			int sum = spaceToFilled; // 채워야 할 빈칸의 갯수
			Queue<Integer> q = new LinkedList<Integer>();
			int[][] d = new int[n][n];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					d[i][j] = -1;

			for (int i = 0; i < virus.size(); i++) { // 선택된 m개 바이러스의 위치를 큐에 삽입
				if (check[i]) {
					q.add(virus.get(i));
					d[virus.get(i) / n][virus.get(i) % n] = 0;
				}
			}
			
			int max = 0; // 이렇게 시뮬레이션 했을 때 바이러스가 전부 퍼지는데 걸리는 시간
			while (!q.isEmpty()) {
				if(sum == 0) break;
				int now = q.remove();
				int x = now / n;
				int y = now % n;
				for (int i = 0; i < 4; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if (nx < 0 || nx >= n || ny < 0 || ny >= n)
						continue;
					if (board[nx][ny] != 1 && d[nx][ny] == -1) {
							d[nx][ny] = d[x][y] + 1;
							q.add(nx * n + ny);
							max = d[nx][ny];
							if(board[nx][ny] == 0) sum--; 
							if(max >= ans) 
								return;
					}
				}
			}
			
			if(sum == 0)
				ans = Math.min(ans, max); // 최소 확산 시간 
			return;
		}

		for (int i = idx; i < virus.size(); i++) {
			check[i] = true;
			dfs(idx + 1, cnt + 1);
			check[i] = false;
		}
	}

}

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

문제

문제

출처

ICPC

시간초과를 피할 수 있는 방법 여쭙습니다

thddudgns79 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말