글 읽기 - else if를 else로 바꿨는데 시간초과 해결에 대해 설명해주실 분 계신가요?

junu_ddi 4년 전 0

시간초과가 나서 아래 코드에 주석처리된 78줄에서 67줄로 변경했더니 시간초과를 해결하였습니다.

단순히 map[ny][nx]가 0인지 아닌지 판단하는 연산하나인데

이게 시간초과가 날지 안 날지를 결정하는 요소가 될 수 있는지 궁금합니다!

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

public class Main {
	private static int n;
	private static int m;
	private static int[][] map;
	private static ArrayList<dot> al;
	private static int min;
	private static int[][][] visit;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	public static void main(String[] args) throws IOException {
		BufferedReader bufferedReader =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stringTokenizer =new StringTokenizer(bufferedReader.readLine());
		
		n= Integer.parseInt(stringTokenizer.nextToken());
		m= Integer.parseInt(stringTokenizer.nextToken());
		
		map = new int[n+1][m+1];
		visit = new int[2][n+1][m+1];
		for(int i=1;i<=n;i++) {
			String s = bufferedReader.readLine();
			for(int j=1;j<=m;j++) {
				int a =  Integer.parseInt(s.substring(j-1,j));
				map[i][j] =a;
				visit[0][i][j] = Integer.MAX_VALUE;
				visit[1][i][j] = Integer.MAX_VALUE;
			}
		}
		min = Integer.MAX_VALUE;
		
		bfs();
		
		System.out.println((min==Integer.MAX_VALUE?-1:min));
	}//main
	static void bfs() {
		Queue<dot> queue = new LinkedList<dot>();
		queue.offer(new dot(1, 1,0,1));
		while(!queue.isEmpty()) {
			dot now = queue.poll();
			int y = now.y; int x = now.x; int move = now.move; int cnt =now.cnt;
			if(move>min) {
				return;
			}
			if(y==n&&x==m) {
				min= Math.min(min, move+1);
				return;
			}
			if(visit[cnt][y][x]<=move) continue;
			visit[cnt][y][x] = move;
			
			for(int i=0;i<4;i++) {
				int ny = y+dy[i]; int nx = x+dx[i];
				//범위
				if(ny<=0||ny>n||nx<=0||nx>m) continue;
			
                
///1. 통과-------------------------------------------------------------------------------------------//                
				if(map[ny][nx]==1) {
					if(cnt==1&&visit[cnt-1][ny][nx]>move+1) {
						queue.offer(new dot(ny, nx, move+1, cnt-1));
					}
				}
				else {
					if(visit[cnt][ny][nx]>move+1) {
						queue.offer(new dot(ny, nx,move+1,cnt));
					}
				}
///2. 시간초과 ---------------------------------------------------------------------------------------//                
//			    if(map[ny][nx]==1&&cnt==1&&visit[cnt-1][ny][nx]>move+1) { //방문하지 않았고  벽이고 아직 뚫을 수 있으면
//					queue.offer(new dot(ny, nx, move+1, cnt-1));
//				}
//				else if(map[ny][nx]==0&&visit[cnt][ny][nx]>move+1) { //방문하지 않았고 일반 길이면
//					queue.offer(new dot(ny, nx,move+1,cnt));
//				}

                
			}
			
		}
		
	}//bfs
	static class dot{
		int y,x,move,cnt;
		public dot(int y, int x, int move, int cnt) {
			super();
			this.y = y;
			this.x = x;
			this.move = move;
			this.cnt = cnt;
		}
	}//dot
}

junu_ddi 4년 전 0

56번째 줄에 < 를 <= 로 바꿔서 시간이 줄어서 해결되었던 것이었습니다. else else if랑은 상관이 없었네요....

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

문제

문제

출처

ICPC

else if를 else로 바꿨는데 시간초과 해결에 대해 설명해주실 분 계신가요?

junu_ddi 4년 전 0

junu_ddi 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말