글 읽기 - 시간 초과가 뜨는데요

anhyunsoo 7년 전 0

while 문안에서 탐색을 진행해서 발생하는 걸까요..

While 안의 이중 for문은 시간초과의 주범이겟죠ㅠ?

입출력 예를 포함해서 몇가지 예에서 맞는 출력값이 나왔습니다.

답자체는 문제가없는데 왜 시간초과가뜰까요

import java.util.Scanner;

public class Main {
	static int[][] a;
	static int m, n, result, l;
	static int[] k;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		n = sc.nextInt();
		l = 1;

		a = new int[m][n];
		for (int j = 0; j < n; j++) {

			for (int i = 0; i < m; i++) {
				int g = sc.nextInt();
				a[i][j] = g;

			}
		}
		while (l != 0) {
			l = 0;    //l을 사용하는것은 go 메소드를 통해 토마토 상태에 변화가 있으면 
			result++; //l값을 변경해주어서 반복문을 실행시키기 위해서 사용했습니다.
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					if (a[i][j] == result)  //결과값을 조건문에 넣은 이유는 두번째 줄에 있는 토마토를 전날 잇던 토마토들에 의해서만 확산을 진행시키기 위함입니다
						go(i, j);          
				}
			}

		}
		result--;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (a[i][j] == 0)
					result = -1;
			}
		}
		System.out.println(result);

	}

	static void go(int i, int j) {

		if (i + 1 != m)
			if (a[i + 1][j] == 0) {
				a[i + 1][j] = 1 + result;
				l++;
			}
		if (j + 1 != n)
			if (a[i][j + 1] == 0) {
				a[i][j + 1] = 1 + result;
				l++;
			}
		if (i > 0 && a[i - 1][j] == 0) {
			a[i - 1][j] = 1 + result;
			l++;
		}
		if (j > 0 && a[i][j - 1] == 0) {
			a[i][j - 1] = 1 + result;
			l++;
		}

	}
}

sgchoi5 7년 전 0

2 ≤ M,N ≤ 1,000 이 크기 때문에 완전탐색으로는 안 되고,

전형적인 BFS 문제입니다. 목적지에 도착하는 단계가 최소 경로(최소 날짜)입니다.

anhyunsoo 7년 전 0

Arraylist 를 이용해서 익은 토마토를 추가시키면서 한번 방문한 토마토는 list에서 제거하면서 코드를 짰는데요
for문을 한개도 안쓰고 풀어봤는데 이렇게해도 시간초과가뜨네요 ㅠㅠ

l, e, u는 result 추가하기 위해 변동되는 횟수를 저장해서 표현하려다보니 상수가 늘어났네요

무시하시고 보셔도 될거같습니다 ㅠㅠ

import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int[][] a;
	static int m, n, result, l, e, u;
	static int[] k;
	static ArrayList<Integer> z, x;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		n = sc.nextInt();
		l = 0;
		u = 0;
		z = new ArrayList<Integer>();
		x = new ArrayList<Integer>();
		a = new int[m][n];

		result = 0;
		for (int j = 0; j < n; j++) {

			for (int i = 0; i < m; i++) {
				int g = sc.nextInt();
				if (g == 1) {
					z.add(i);
					x.add(j);
				} else if (g == 0)
					u++;
				a[i][j] = g;

			}
		}
		e = z.size();

		while (z.size() != 0) {

			go(z.get(0), x.get(0));
			e--;
			if (e == 0) {
				result++;
				e = l;
				l = 0;
			}
			z.remove(0);
			x.remove(0);
		}

		result--;

		if (u != 0)
			result = -1;

		System.out.println(result);

	}

	static void go(int i, int j) {

		if (i + 1 != m)
			if (a[i + 1][j] == 0) {
				a[i + 1][j] = 1;
				z.add(i + 1);
				x.add(j);
				l++;
				u--;
			}
		if (j + 1 != n)
			if (a[i][j + 1] == 0) {
				a[i][j + 1] = 1;
				z.add(i);
				x.add(j + 1);
				l++;
				u--;
			}
		if (i > 0 && a[i - 1][j] == 0) {
			a[i - 1][j] = 1;
			z.add(i - 1);
			x.add(j);
			l++;
			u--;
		}
		if (j > 0 && a[i][j - 1] == 0) {
			a[i][j - 1] = 1;
			z.add(i);
			x.add(j - 1);
			l++;
			u--;
		}

	}
}

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

문제

문제

출처

ICPC

시간 초과가 뜨는데요

anhyunsoo 7년 전 0

sgchoi5 7년 전 0

anhyunsoo 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말