글 읽기 - [JAVA]시간초과를 어떻게 해결하나요??

godhpjh123 4년 전 0

1% 에서 시간초과가 납니다.

도와주세요!

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

public class Main {
	
	static int N, M, S, E, answer;
	static Telpo[] telpo;
	
	private static class Telpo {
		int from;
		int to;
		public Telpo(int from, int to) {
			super();
			this.from = from;
			this.to = to;
		}
	}
	
	private static class Move {
		int num;
		int count;
		public Move(int num, int count) {
			super();
			this.num = num;
			this.count = count;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 1. 입력
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());  // 최대 정거장
		M = Integer.parseInt(st.nextToken());  // 텔레포트정거장 수
		
		st = new StringTokenizer(in.readLine(), " ");
		S = Integer.parseInt(st.nextToken());  // 시작 위치
		E = Integer.parseInt(st.nextToken());  // 도착 위치
		
		telpo = new Telpo[M];
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to   = Integer.parseInt(st.nextToken());
			telpo[i] = new Telpo(from, to);
		}
		
		// 2. BFS
		bfs();
		
		// 3. 정답 출력
		System.out.println(answer);
	}
	
	public static void bfs() {
		Queue<Move> que = new LinkedList<Move>();
		boolean[] visited = new boolean[N+1]; ;
		que.offer(new Move(S, 0));
		visited[S] = true;
		
		while(!que.isEmpty()) {
			Move m = que.poll();
			int num = m.num;
			int count = m.count;
			
			if(num == E) {	// 도착 지점 확인
				answer = count;
				break;
			}
			
			// 1) -1
			if(num-1 >= 1 && !visited[num-1]) {
				visited[num-1] = true;
				que.offer(new Move(num-1, count+1));
			}
			// 2) +1
			if(num+1 <= N && !visited[num+1]) {
				visited[num+1] = true;
				que.offer(new Move(num+1, count+1));
			}
			// 3) Teleport
			for(int i=0; i<M; i++) {
				if(telpo[i].to > N || visited[telpo[i].to]) continue; // 한번 텔포한 정거장은 또 볼 필요가 없다.
				if(telpo[i].from == num) { // 텔포가 가능한 자리면 시도
					visited[telpo[i].to] = true;
					que.offer(new Move(telpo[i].to, count+1));
				}
			}
		}
	}
	
}

godhpjh123 4년 전 1

다음과 같은 부분들을 이해하고 푸니 해결하였습니다.

1. 양방향이라는 것. (단방향으로 풀었었음..)

2. 모든 케이스마다 M만큼 검사하므로 시간초과가 났음.

이문제를 해곃하기 위해 N사이즈 만큼 Telpo클래스를 ArrayList로 따로 맵을 만들어 푸니 해결하였습니다.

M만큼 모든검사를 하지 않고 해당 텔포가능한 부분 사이즈만 확인할 수 있도록 변경하였습니다.

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

문제

문제

출처

ICPC

[JAVA]시간초과를 어떻게 해결하나요??

godhpjh123 4년 전 0

godhpjh123 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말