글 읽기 - 시간초과 도와주세요 ..

dlcksdnd321 4년 전 0

배양액 자리 조합 + 배양액 색깔뿌리기 조합 + 배양액 진행 bfs 했는데

시간초과가 생깁니다. .. 왜 시간초과인지 잘 모르겠습니다. 돠와주세요 ㅠㅠㅠ

package Samsung;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B18809 {
	static int N, M, G, R;
	static int[][] map;
	static int result = 0;
	static ArrayList<gardenloc> possible = new ArrayList();
	static gardenloc[] temp;
	static boolean[] temp2;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	static int cnt = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		G = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		temp = new gardenloc[R + G];
		temp2 = new boolean[R + G];
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			String[] str = bf.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(str[j]);
				if (map[i][j] == 2)
					possible.add(new gardenloc(i, j));
			}
		}
		dfs(0, 0);
		System.out.println(result);
	}

	static void dfs(int index, int cnt) {
		if (cnt == R + G) {
			// 현재 temp에는 배양액을 뿌릴 자리가 결정되있음
			// for (int i = 0; i < temp.length; i++)
			// System.out.print(temp[i].r + "," + temp[i].c + " ");
			// System.out.println();
			dfs2(0, 0);
			return;
		}
		if (index == possible.size())
			return;
		temp[cnt] = possible.get(index); 
		dfs(index + 1, cnt + 1);
		dfs(index + 1, cnt);
	}

	static void dfs2(int index, int cnt) {
		if (cnt == R) {
			// for(int i = 0 ; i < temp2.length; i++)
			// System.out.print(temp2[i]+" ");
			// System.out.println();
			solve();
			return;
		}
		if (index == temp.length)
			return;
		temp2[index] = true;
		dfs2(index + 1, cnt + 1);
		temp2[index] = false;
		dfs2(index + 1, cnt);
	}

	static void solve() {
		cnt++;
		boolean see = false;
		// 현재 temp에는 배양액을 뿌릴 자리가 결정되있음
		// 현재 temp2에는 빨간 배양액 뿌릴 자리가 결정되어있음
		int[][] mapClone = new int[N][M];
		for (int i = 0; i < N; i++)
			mapClone[i] = Arrays.copyOf(map[i], M);
		boolean[][] visit = new boolean[N][M];
		Queue<water> q = new LinkedList();
		for (int i = 0; i < temp.length; i++) {
			if (temp2[i]) {
				q.add(new water(temp[i].r, temp[i].c, 3));
				mapClone[temp[i].r][temp[i].c] = 3;
				visit[temp[i].r][temp[i].c] = true;
			} else {
				q.add(new water(temp[i].r, temp[i].c, 4));
				mapClone[temp[i].r][temp[i].c] = 4;
				visit[temp[i].r][temp[i].c] = true;
			}
		}
		while (!q.isEmpty()) {
			int[][] activate = new int[N][M];
			int size = q.size();
			for (int i = 0; i < size; i++) {
				water now = q.poll();
				if (mapClone[now.r][now.c] == 7)
					continue;
				for (int move = 0; move < 4; move++) {
					int nextR = now.r + dr[move];
					int nextC = now.c + dc[move];
					if (nextR < 0 || nextR >= N || nextC >= M || nextC < 0)
						continue;
					if (mapClone[nextR][nextC] == 0 || mapClone[nextR][nextC] == 7)
						continue;
					if ((now.color == 3 && activate[nextR][nextC] == 4)
							|| (now.color == 4 && activate[nextR][nextC] == 3)) {
						mapClone[nextR][nextC] = 7;
						visit[nextR][nextC] = true;
						continue;
					}
					if (mapClone[nextR][nextC] == 3 || mapClone[nextR][nextC] == 4)
						continue;
					if (visit[nextR][nextC])
						continue;

					q.add(new water(nextR, nextC, now.color));
					if (now.color == 3) {
						mapClone[nextR][nextC] = 3;
						activate[nextR][nextC] = 3;
					} else {
						mapClone[nextR][nextC] = 4;
						activate[nextR][nextC] = 4;
					}
					visit[nextR][nextC] = true;
				}
			}
		}
		int res = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (mapClone[i][j] == 7)
					res++;
			}
		}

		result = res > result ? res : result;
	}
}

class water {
	int r, c, color;

	public water(int r, int c, int color) {
		this.r = r;
		this.c = c;
		this.color = color;
	}
}

class gardenloc {
	int r, c;

	public gardenloc(int r, int c) {
		this.r = r;
		this.c = c;
	}
}

tristan3716 4년 전 1

solve 함수의 배열 초기화를 arraycopy로 변경 후 생각보다 여유롭게 AC를 받을 수 있긴합니다만,

activate 관련 처리가 다소 비효율적인듯 합니다. 구조를 조금 바꾸면 activate 배열을 사용하지않거나, 한번만 초기화해서 문제를 풀 수 있습니다.

dlcksdnd321 4년 전 0

도움주셔서 감사합니다. 다시한번 생각해보겠습니다!

dlcksdnd321 4년 전 1

@tristan3716 덕분에 맞았습니다 감사합니다.

tmakdlf2770 3년 전 0

저도 이렇게 풀었는데 혹시 시간초과 어떻게 해결하셨나요??

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

문제

문제

출처

ICPC

시간초과 도와주세요 ..

dlcksdnd321 4년 전 0

tristan3716 4년 전 1

dlcksdnd321 4년 전 0

dlcksdnd321 4년 전 1

@tristan3716 덕분에 맞았습니다 감사합니다.

tmakdlf2770 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말