글 읽기 - 안녕하세요. JAVA로 토마토문제가 시간초과가 떠서 질문 드립니다.

jsjouo249 3년 전 0

해당 문제를 풀면서...2%에서 시간초과가 떠서 질문 드립니다.

Queue로 풀고, 토마토가 익어가면서, Queue가 안비어있어도 토마토가 다 익었다면 미리 return으로 종료 시키는 86~87 방법도 고려해서 넣었습니다.

하지만 저게 문제가 아닌거 같고, visit[][]배열도 처음엔 사용을 했었지만, 토마토가 1로 바뀌는 시점에서 visit의 역할도 같이 하는 것 같고, 시간초과 관련된 문제점일까 해서 제외 했습니다....

주석을 최대한 달았지만... 난잡한 소스를 보시고 혹시 소스의 문제점이나 에러에 대해 알려주시면 감사하겠습니다.

글 읽어주셔서 감사합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class position{

	int x, y, days;

	position(int x, int y, int days) {
		this.x    = x;
		this.y 	  = y;
		this.days = days;
	}
}

public class Main {

	static int[] moveX = { 0, 1,  0, -1};
	static int[] moveY = { 1, 0, -1,  0};

	public static void main(String[] args) throws IOException{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str = br.readLine();
		int m = Integer.parseInt( str.split(" ")[0] );
		int n = Integer.parseInt( str.split(" ")[1] );

		int tomatos = 0;		//익지 않은 토마토 갯수
		int compareTomatos = 0; //bfs를 하면서 익어가는 토마토 갯수

		int answer = 0;			//지난 일 수

		int[][] tomato = new int[n][m];

		Queue<position> que = new LinkedList();

		//토마토 배열에 넣기
		for(int i = 0; i < n; i++) {
			str = br.readLine();
			for(int j = 0; j < m; j++) {
				tomato[i][j] = Integer.parseInt( str.split(" ")[j] );

				//que에 익은 토마토 넣기
				if( tomato[i][j] == 1 ) {
					position pos = new position( i, j, 0 );
					que.add( pos );

				}

				if( tomato[i][j] == 0 ) {
					tomatos++;
				}
			}
		}

		System.out.println( bfs( que, tomato, tomatos, compareTomatos, answer, n, m ) );
	}

	public static int bfs( Queue<position> que, int[][] tomato, int tomatos, int compareTomatos, int answer, int n, int m ) {
		//bfs로 근처의 토마토 익으면서 더 이상 안익은 토마토 없을 때 까지 반복
		while( !que.isEmpty() ) {

			position thisPos = que.poll();

			int thisX = thisPos.x;
			int thisY = thisPos.y;
			answer  = thisPos.days;

			//우하좌상의 토마토 찾기
			for(int i = 0; i < moveX.length; i++) {
				int nextX = thisX + moveX[i];
				int nextY = thisY + moveY[i];

				//배열 범위 안에서
				if( nextX >= 0 && nextY >= 0 && nextX < n && nextY < m ) {
					if( tomato[nextX][nextY] == 0 /*&& visit[nextX][nextY] == false*/ ) {
//						visit[nextX][nextY]  = true;
						tomato[nextX][nextY] = 1;
						position nextPos = new position( nextX, nextY, answer+1 );
						que.add( nextPos );
						compareTomatos++;

						//토마토가 다 익었으면, bfs 종료한 뒤, 하루 지난 일 더하기
						if( tomatos == compareTomatos ) {
							return (answer+1);
						}
					}
				}
			}
		}

		return -1;
	}


}

exponential_e 3년 전 1

시간초과에 대한 말씀을 드리기 전에 일단 아래의 예시에서 제대로된 답을 내놓지 못합니다.

시간초과는 제 생각엔 split이 아닌 StringTokenizer를 사용하시면 될 것 같습니다. 생각보다 차이가 많이 나니 관련해서 찾아보시거나 테스트 해보시면 좋을 듯 합니다.

또한, 실제로 작성자님이 주신 코드를 split -> StringTokenizer로만 수정해봤는데, 해당 코드가 100%에서 '틀렸습니다' 판정을 받았습니다. 즉 시간초과는 나지 않는 것으로 보입니다.

(채점번호: https://www.acmicpc.net/source...)

jsjouo249 3년 전 1

exponential_e

친절한 답변 달아주셔서 감사합니다.

StringTokenizer보다 split이 더 편해서 썼었는데 알려주신 내용을 토대로 공부해보겠습니다.

감사합니다.

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

문제

문제

출처

ICPC

안녕하세요. JAVA로 토마토문제가 시간초과가 떠서 질문 드립니다.

jsjouo249 3년 전 0

exponential_e 3년 전 1

jsjouo249 3년 전 1

exponential_e

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말