글 읽기 - java 시간초과납니다...

spide333 5년 전 0

시간초과가 나는데 어떻게 해야할지 모르겠어요ㅠㅠ

처음에 맾에 모든 길에 얼마 뒤에 물이 찰 지를 구해서 map[][]에 그 값을 저장하고

그 이후에 bfs를 돌렸는데... 시간초과가 납니다.

당연히 날것같긴 했는데;; 시간초과를 어떻게 해결할 수 있을까요??

아예 코드를 싹 뒤엎어야 할까요?

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

public class Main{
	static int R, C;
	static Queue<int[]> qu = new LinkedList<int[]>();
	static int v[][], map[][], temp, sx, sy, ans;
	static int dx[] = {0,0,1,-1};
	static int dy[] = {1,-1,0,0};
	static boolean arrive;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();
		C = sc.nextInt();
		map = new int[R][C];
		arrive = false;
		ans = R*C;
		for(int i=0;i<R;i++) {
			String input = sc.next();
			for(int j=0;j<C;j++) {
				if(input.charAt(j)=='D') map[i][j]=-1; // -1 : 목적지 
				else if(input.charAt(j)=='S') {
					map[i][j]=-2; // 0 : 시작점
					sx = i;
					sy = j;
				}
				else if(input.charAt(j)=='X') map[i][j]=-3; // -3 : 돌
				else if(input.charAt(j)=='.') map[i][j]=-2; // -2 : 길가
				else if(input.charAt(j)=='*') map[i][j]=-4; // -4 : 물
			}
		}
		
		
		for(int i=0;i<R;i++) {
			for(int j=0;j<C;j++) {
				temp = R*C;
				v = new int[R][C];
				if(map[i][j]==-2) {
					dist(i, j, 0);
					map[i][j]=copy(temp);
				}
			}
		}
		//printmap();
		qu.add(new int[]{sx,sy,0});
		while(!qu.isEmpty()) {
			int[] x = qu.poll();
			int xx = x[0];
			int yy = x[1];
			int tt = x[2];
			
			for(int i=0;i<4;i++) {
				int nx = xx+dx[i];
				int ny = yy+dy[i];
				if(nx<0||nx>=R||ny<0||ny>=C) continue;
				if(v[nx][ny]==0&&map[nx][ny]>tt+1) {
					v[nx][ny]=1;
					qu.add(new int[] {nx,ny,tt+1});
				}
				else if(map[nx][ny]==-1) {
					ans =Math.min(tt+1, ans);
					arrive = true;
					break;
				}
			}
		}
		
		if(arrive) {
			System.out.println(ans);
		}
		else {
			System.out.println("KAKTUS");
		}
		
	}
	static int copy(int x) {
		return x;
	}
	static void dist(int x, int y, int dis) { //각 위치마다 얼마뒤에 물이 찰 지 구하는 함수
		if(map[x][y]>0) {
			temp=Math.min(temp,  map[x][y]+dis); //이미 앞에서 구했다면 그 값 이용
		}
		else {
			for(int i=0;i<4;i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(nx<0||nx>=R||ny<0||ny>=C) continue;
				if(map[nx][ny]==-1||map[nx][ny]==-3) continue;
				if(map[nx][ny]==-4) {
					temp=Math.min(temp, dis+1); //물에 도착했을 경우
				}
				else if(v[nx][ny]==0) {
					v[nx][ny]=1;
					dist(nx,ny,dis+1);
					v[nx][ny]=0;
				}
			}
		}
	}
	static void printmap() {
		for(int i=0;i<R;i++) {
			for(int j=0;j<C;j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println(" ");
		}
	}
}

luniro 5년 전 0

dist 돌리는 과정에서 발생할 것 같습니다 말씀하신 논리로는 시간초과가 발생하지 않아요

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

문제

문제

출처

ICPC

java 시간초과납니다...

spide333 5년 전 0

luniro 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말