글 읽기 - 시간초과 질문드려요

c6369 7년 전 0

큐에다가 집어넣고 마지막 출구에 도달했을때 cnt 값을 비교해서

가장 작은값을 출력하는 식으로 코드를 짰는데 역시 시간 초과가 나옵니다 ㅠㅠ

어떻게 수정하면 좋을까요?

고수님들 도와주세요!

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	
	private static int N;
	private static int M;
	
	private static int[] dx = {0,1,0,-1};
	private static int[] dy = {1,0,-1,0};
	
	private static int map[][];
	private static boolean memo[][];
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		M = sc.nextInt();
		N = sc.nextInt();
		
		map = new int[N][M];
		memo = new boolean[N][M];
		
		
		for(int i=0; i<N; i++){
			String str = sc.next();
			for(int j=0; j<M; j++){
				map[i][j] = str.charAt(j)-48;
			}
		}
		
		bfs(0,0,0);
		
	}
	
	private static void bfs(int x, int y,int cnt){
		Queue<N1261> q = new LinkedList<N1261>();
		N1261 node = new N1261(x,y,cnt);
		memo[x][y] = true;
		q.offer(node);
		
		int min = Integer.MAX_VALUE;
		
		while(!q.isEmpty()){
			N1261 cur = q.peek();
			q.poll();
			memo[cur.x][cur.y] = true;	
			
			if((cur.x==N-1)&&(cur.y==M-1)){
				if(min>cur.cnt) min = cur.cnt;
			}
			N1261 child = null;
			
			for(int i=0; i<4; i++){
				if(isSafe(cur.x+dx[i],cur.y+dy[i])&&(memo[cur.x+dx[i]][cur.y+dy[i]]==false)){
					if(map[cur.x+dx[i]][cur.y+dy[i]]==1){
						child = new N1261(cur.x+dx[i],cur.y+dy[i],(cur.cnt)+1);
						q.offer(child);
					}else{
						child = new N1261(cur.x+dx[i],cur.y+dy[i],(cur.cnt));
						q.offer(child);
					}
				}
			}
			
		}
		System.out.println(min);
	}
	
	private static boolean isSafe(int x, int y){
		if((x<N&&x>=0)&&(y<M&&y>=0)){
			return true;
		}else{
			return false;
		}
	}
	
	

}
class N1261{
	int x;
	int y;
	int cnt;
	public N1261(int x, int y,int cnt){
		this.x = x;
		this.y = y;
		this.cnt = cnt;
	}
}

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

문제

문제

출처

ICPC

시간초과 질문드려요

c6369 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말