글 읽기 - 시간초과가 왜 나올까요..?ㅠㅠ

roland91 6년 전 0

최대한 줄인 거 같은데 왜 시간초과가 나올까요..?

import java.io.*;
import java.util.*;

public class Main {
	final static int UP = -1, DOWN = 1, LEFT = -1, RIGHT = 1;
	static Queue<Integer[]> q = new LinkedList<>();
	static int[][] tomatoes;
	static int day = 0;
	static int total;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] whStrArr = br.readLine().split(" ");
		int width = Integer.parseInt(whStrArr[0]);
		int height = Integer.parseInt(whStrArr[1]);
		tomatoes = new int[height][width];
		total = height * width;
		for (int i = 0; i < height; i++) {
			whStrArr = br.readLine().split(" ");
			for (int j = 0; j < whStrArr.length; j++) {
				tomatoes[i][j] = Integer.parseInt(whStrArr[j]);
				if (tomatoes[i][j] == 1) {
					Integer[] t = { i, j, day };
					q.add(t);
					total--;
				} else if (tomatoes[i][j] == -1) {
					total--;
				}
			}
		}
		while (!q.isEmpty()) {
			bfs(q.remove());
		}
		if (total == 0) {
			System.out.println(day);
		} else {
			System.out.println(-1);
		}

	}

	static public void bfs(Integer[] t) {
		if (tomatoes[t[0]][t[1]] == -1) {
			return;
		} else if (tomatoes[t[0]][t[1]] == 0) {
			total--;
			tomatoes[t[0]][t[1]] = 1;
		}
		if (t[0] + UP >= 0) {
			if (tomatoes[t[0] + UP][t[1]] == 0) {
				Integer[] t1 = { t[0] + UP, t[1], t[2] + 1 };
				day = t[2] + 1;
				q.add(t1);
			}
		}
		if (t[0] + DOWN < tomatoes.length) {
			if (tomatoes[t[0] + DOWN][t[1]] == 0) {
				Integer[] t1 = { t[0] + DOWN, t[1], t[2] + 1 };
				day = t[2] + 1;
				q.add(t1);
			}
		}
		if (t[1] + LEFT >= 0) {
			if (tomatoes[t[0]][t[1] + LEFT] == 0) {
				Integer[] t1 = { t[0], t[1] + LEFT, t[2] + 1 };
				day = t[2] + 1;
				q.add(t1);
			}
		}
		if (t[1] + RIGHT < tomatoes[0].length) {
			if (tomatoes[t[0]][t[1] + RIGHT] == 0) {
				Integer[] t1 = { t[0], t[1] + RIGHT, t[2] + 1 };
				day = t[2] + 1;
				q.add(t1);
			}
		}
	}
}

sgchoi5 6년 전 1

BFS 방식을 이용할 때에 queue 에 넣고, 다음을 찾고 하는 구조에서 이미 한 번 큐에 넣은 것은 다시 사용하지 않도록 처리를 해주어야 합니다.

아마 그게 안되어 있어서 중복 연산을 많이 하는 듯 하네요.

M, N 크기가 작으면 문제 없는 듯 보이지만, 커지면 시간 초과가 생길 겁니다.

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

문제

문제

출처

ICPC

시간초과가 왜 나올까요..?ㅠㅠ

roland91 6년 전 0

sgchoi5 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말