글 읽기 - 미로찾기 BFS 시간을 줄일곳이 있는지 조언 부탁드립니다.

kepler710 7년 전 0

x,y좌표를 큐에 넣어가며 미로찾기를 하고있습니다.

각 좌표까지의 거리를 min이라는 배열에 업데이트 시켜주며 연산을 합니다.

큐에서 빼낸 점이 4가지 방향으로 갈 수 있는지 조사하며 큐에 넣어주고있습니다.

조건검사로는 3가지가있는데 위로 갈 수 있는 경우를 예로들었을 경우 처음조건부터

1. 인덱스를 초과하는지

2. 이 점을 방문 했었는지

3. 해당 방향으로 길이 있는지

를 조사하며 해당 도착점에 도달했을경우 빠져나오도록 구현했습니다.

답은 올바르게 출력되는듯 하나 시간초과가 뜨네요.

고수님들의 조언 부탁드립니다.

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 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] arr = new int[N][M];
		boolean[][] visited = new boolean[N][M];
		int[][] min = new int[N][M];
		
		for(int i=0; i<arr.length; i++){
			String a = br.readLine();
			for(int j=0; j<arr[0].length; j++){
				arr[i][j] = (a.charAt(j))-48;
			}
		}
		
		Queue<Integer> x = new LinkedList<Integer>();
		Queue<Integer> y = new LinkedList<Integer>();
		
		x.offer(0);
		y.offer(0);
		min[0][0] = 1;
		
		while(!x.isEmpty()){
			int cx = x.poll();
			int cy = y.poll();
			visited[cx][cy] = true;
			//도달
			if(cx==N-1 && cy==M-1){
				System.out.println(min[cx][cy]);
				break;
			}
			//위로 갈수있는경우
			if( cx-1>-1 && !visited[cx-1][cy] && arr[cx-1][cy]==1){
				x.offer(cx-1);
				y.offer(cy);
				min[cx-1][cy]=min[cx][cy]+1;
			}
			//아래
			if( cx+1<N && !visited[cx+1][cy] && arr[cx+1][cy]==1){
				x.offer(cx+1);
				y.offer(cy);
				min[cx+1][cy]=min[cx][cy]+1;
			}
			//좌
			if( cy-1>-1 && !visited[cx][cy-1] && arr[cx][cy-1]==1){
				x.offer(cx);
				y.offer(cy-1);
				min[cx][cy-1]=min[cx][cy]+1;
			}
			//우
			if( cy+1<M && !visited[cx][cy+1] && arr[cx][cy+1]==1){
				x.offer(cx);
				y.offer(cy+1);
				min[cx][cy+1]=min[cx][cy]+1;
			}
		}		
	}
}

alice 7년 전 1

while문 안에 있는 상하좌우 if문 안에다가도 visited = true;를 넣어보세요

visited를 일일이 체크해주느라 시간 초과가 생기는 것으로 보입니다

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

문제

문제

출처

ICPC

미로찾기 BFS 시간을 줄일곳이 있는지 조언 부탁드립니다.

kepler710 7년 전 0

alice 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말