글 읽기 - 나름 BFS로 짰다고 생각하는데 시간초과가 나네요..ㅜㅜ

nbpryun 7년 전 0

자꾸자꾸 시간초과 나요 ㅜㅜ

제가 생각하기에는 제가 짠 코드가 전형적인 BSF라 생각되는데

혹시 시간초과 날만한 이유가 있나요?

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

 class baekjoon2178 
{
	public baekjoon2178(){}
	public void test()
	{
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int M = in.nextInt();
		int[][] miro = new int[N][M];
		boolean[][] visit = new boolean[N][M];
		String forInput;
		for(int i = 0; i < N; i++)
		{
			forInput = in.next();
			for(int j = 0; j < M; j ++)
			{
				miro[i][j] = (int) forInput.charAt(j) - '0';
				visit[i][j] = false;
			}
		}
		Queue<Integer> Q = new LinkedList<Integer>();
		Q.offer(0);
		Q.offer(0);
		Q.offer(0);
		int x, y, l;
		int result = -1;
		while(!Q.isEmpty())
		{	
			x = Q.poll();
			y = Q.poll();
			l = Q.poll();
			result = l;
			if(x > 0 && miro[x-1][y] == 1 && visit[x-1][y] == false)
			{
				Q.offer(x-1);
				Q.offer(y);
				Q.offer(l+1);
			}
			if(y > 0 && miro[x][y-1] == 1 && visit[x][y-1] == false)
			{
				Q.offer(x);
				Q.offer(y-1);
				Q.offer(l+1);
			}
			if(x < N-1 && miro[x+1][y] == 1 && visit[x+1][y] == false)
			{
				Q.offer(x+1);
				Q.offer(y);
				Q.offer(l+1);
			}
			if(y < M-1 && miro[x][y+1] == 1 && visit[x][y+1] == false)
			{
				Q.offer(x);
				Q.offer(y+1);
				Q.offer(l+1);
			}
		
		}
		System.out.println(result + 1); //dd
		
	}
}

public class Main 
{

	public static void main(String[] args) 
	{
		baekjoon2178 hi = new baekjoon2178();
		hi.test();
	}

}

sunhong 7년 전 1

true 체크 안해주셨네요 그리고 empty까지 돌리면 만약에 더큰 result 값이 오면 바뀔수도 있겠네요.

nbpryun 7년 전 0

음..true체크하고 empty전에 break걸어도 시간초과떠여 ..ㅜㅜ

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

public class baekjoon2178 
{
	public baekjoon2178(){}
	public void test()
	{
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int M = in.nextInt();
		int[][] miro = new int[N][M];
		boolean[][] visit = new boolean[N][M];
		String forInput;
		for(int i = 0; i < N; i++)
		{
			forInput = in.next();
			for(int j = 0; j < M; j ++)
			{
				miro[i][j] = (int) forInput.charAt(j) - '0';
				visit[i][j] = false;
			}
		}
		Queue<Integer> Q = new LinkedList<Integer>();
		Q.offer(0);
		Q.offer(0);
		Q.offer(0);
		int x, y, l;
		int result = -1;
		while(!Q.isEmpty())
		{	
			x = Q.poll();
			y = Q.poll();
			l = Q.poll();
			result = l;
			if(x == N-1 && y == M-1)
				break;
			if(!visit[x][y])   
            {
	    		visit[x][y] = true;
	    		if(x > 0 && miro[x-1][y] == 1 && visit[x-1][y] == false)
		    	{
			    	Q.offer(x-1);
				    Q.offer(y);
				    Q.offer(l+1);
			    }
    			if(y > 0 && miro[x][y-1] == 1 && visit[x][y-1] == false)
	    		{
	    			Q.offer(x);
	    			Q.offer(y-1);
	    			Q.offer(l+1);
	    		}
	    		if(x < N-1 && miro[x+1][y] == 1 && visit[x+1][y] == false)
	    		{
	    			Q.offer(x+1);
	    			Q.offer(y);
	    			Q.offer(l+1);
	    		}
	    		if(y < M-1 && miro[x][y+1] == 1 && visit[x][y+1] == false)
	    		{
	    			Q.offer(x);
	    			Q.offer(y+1);
	    			Q.offer(l+1);
		    	}
			}
		
		}
		System.out.println(result + 1); //dd
		
	}
}

sunhong 7년 전 2

true 체크는 바로해주셔야 중복으로 큐에 안들어가구요

일부니까 참고하세여

		int[][] miro = new int[N+10][M+10];
		boolean[][] visit = new boolean[N+10][M+10];
		int[][] cnt= new int[N+10][M+10];
		int[] dx={0,0,1,-1,1,-1,0,0};

		Q.offer(1);
		Q.offer(1);
		int x, y;
		while(!Q.isEmpty()){	
			x = Q.poll();
			y = Q.poll();
			visit[x][y]=true;
			for(int i=0;i<4;i++){
	    		if((miro[x+dx[i]][y+dx[i+4]] == 1) && (visit[x+dx[i]][y+dx[i+4]] == false)){
	    			cnt[x+dx[i]][y+dx[i+4]]=cnt[x][y]+1;
			    	Q.offer(x+dx[i]);
				    Q.offer(y+dx[i+4]);
				    visit[x+dx[i]][y+dx[i+4]]=true;
			    }
			}
		}
		System.out.println(cnt[N][M] + 1);

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

문제

문제

출처

ICPC

나름 BFS로 짰다고 생각하는데 시간초과가 나네요..ㅜㅜ

nbpryun 7년 전 0

sunhong 7년 전 1

nbpryun 7년 전 0

sunhong 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말