글 읽기 - 시간 초과가 나는 이유를 모르겠습니다.

yooil405 1년 전 0

2초의 여유시간이 있고

시간복잡도를 계산해 봤을 때, 제가 작성한 코드가 N*M*K = 10^7 정도로 추정되는데.., 1초당 약 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;

// 벽 부수고 이동하기 2
public class Main {
	static class Place {
		int y;
		int x;
		int dis;
		int drill;
		
		
		
		public Place(int y, int x, int dis, int drill) {
			this.y = y;
			this.x = x;
			this.dis = dis;
			this.drill = drill;
		}
	}
	
	private static int N;
	private static int M;
	static int[] dy = {1, -1, 0, 0};
	static int[] dx = {0, 0, 1, -1};
	private static int[][] matrix;
	private static int res;
	private static int K;
	private static int[][] isVisit;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		matrix = new int[N][M];
		isVisit = new int[N][M];
		String S = "";
		
		
		for (int i = 0; i < matrix.length; i++) {
			S = br.readLine(); 
			for (int j = 0; j < matrix[i].length; j++) {
				int n = S.charAt(j) - 48;
				matrix[i][j] = n;
				isVisit[i][j] = Integer.MAX_VALUE;
			}
		}
		
		res = Integer.MAX_VALUE;
		bfs(0, 0);
		
		if (res == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(res);
		
		
	}

	private static void bfs(int y, int x) {
		Queue<Place> q = new LinkedList<>();
		q.add(new Place(y, x, 1, 0)); // 순서대로 x, y, 부셨는지?, 거리
		isVisit[y][x] = 0;
		
		while(!q.isEmpty()) {
			Place temp = q.poll();
			
			if(temp.y == N - 1 && temp.x == M - 1) {
				res = temp.dis;
				break;
			}
			
			for(int i = 0; i < 4; i++) {
				int ny = temp.y + dy[i];
				int nx = temp.x + dx[i];
				
				if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
				// isVisit 배열의 값은 공사횟수이다. 만약 다음에 나온 공사횟수가 기존 갖고 있던 값보다 작거나 같다는 것은
				// 더 적은 공사횟 수를 한 것이 이미 그 자리를 더 적은 레벨로 지나갔다는 것임으로 배제해 준다.
				// 반대로 isVisit이 더 크다는 소리는 더 많은 공수횟수를 갖은 것이 더 적은 레벨로 그 자리를 지나갔다는 것이다.
				// 이 경우에는 그 경우가 가다가 막힐 가능성이 있으므로 큐에 넣어준다.
				if(isVisit[ny][nx] <= temp.drill) continue;
				
				// 벽이 아닌 경우
				if(matrix[ny][nx] == 0) {
					isVisit[ny][nx] = temp.drill;
					q.add(new Place(ny, nx, temp.dis + 1, temp.drill));
				}
				
				// 벽인 경우
				else {
					if(temp.drill < K) {
						isVisit[ny][nx] = temp.drill + 1;
						q.add(new Place(ny, nx, temp.dis + 1, temp.drill + 1));
					}
				}
			}
		}
	}
}

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

문제

문제

출처

ICPC

시간 초과가 나는 이유를 모르겠습니다.

yooil405 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말