글 읽기 - BFS 시간초과 ㅜㅜ

wicked91j 7년 전 0

BFS방식으로 Queue를 이용해 해결하려고 했는데

18% 쯤에서 시간초과 오류가 뜹니다.

문제의 답은 정확히 나오는데 어느부분에서 시간을 줄여야 할까요??

도움 부탁드립니다.

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

class MapInfo{
	int x,y,Level;
	MapInfo(int x, int y, int Level){
		this.x=x;
		this.y=y;
		this.Level=Level;
	}
}

public class Maze_Search_2178 {

	static int N,M;
	static int Map[][];
	static Queue<MapInfo> q;
	
	public static void BFS(int n, int m){
		
		q.offer(new MapInfo(n,m,1));
		MapInfo POP;
		
		while(!q.isEmpty()){
			POP = q.poll();
			int X = POP.x;
			int Y = POP.y;
			int Level = POP.Level;
		
			if(X==N && Y==M && Map[X][Y]==1){
				System.out.println(Level);
				break;
			}
			if(X-1>0 && Map[X-1][Y]==1){
				q.offer(new MapInfo(X-1,Y,Level+1));
			}
			if(X+1<=N && Map[X+1][Y]==1){
				q.offer(new MapInfo(X+1,Y,Level+1));
			}
			if(Y-1>0 && Map[X][Y-1]==1){
				q.offer(new MapInfo(X,Y-1,Level+1));
			}
			if(Y+1<=M && Map[X][Y+1]==1){
				q.offer(new MapInfo(X,Y+1,Level+1));
			}
			Map[X][Y]++;
		}
	}
	
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(System.in);
		String str;
		N=sc.nextInt();
		M=sc.nextInt();
		
		Map = new int[N+1][M+1];
		q = new LinkedList<MapInfo>();
	
		for(i=1;i<=N;i++){
			str = sc.next();
			for(j=1;j<=M;j++){
				Map[i][j]=Integer.parseInt(str.charAt(j-1)+"");
			}
		}
		BFS(1,1);		
	}

}

jwg8679 7년 전 0

visited 배열 사용하셔서 기 방문 노드는 재방문하지 않으시면 시간초과 안 뜰거같습니다

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

문제

문제

출처

ICPC

BFS 시간초과 ㅜㅜ

wicked91j 7년 전 0

jwg8679 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말