글 읽기 - 시간초과나는이유가 뭘까

yeeeah_j 6년 전 0

bfs이용해서 풀엇습니다.

시간초과 나는이유를 모르겟습니다.

package beak5427;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	final static String SPACE = " ";
	static char map[][];
	static int fireMap[][];
	static int isVisited[][];
	static int[][] DIRECTIONS ={{0,1},{0,-1},{1,0},{-1,0}};
	static Point start ;


	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader( new InputStreamReader (System.in));
		int testCase = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		while(testCase-- >0){
			st =new StringTokenizer(br.readLine(),SPACE);
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			
			map= new char[x][y];
			fireMap = new int[x][y];
			isVisited = new int[x][y];
			
			for(int i =0; i <x; i++){
				String line = br.readLine();
				for(int j =0; j <y; j++){
					char mapChar = line.charAt(j);
					map[i][j]= mapChar;
					if(mapChar =='@'){
						start = new Point(i,j);
					}else if(mapChar == '*' )
						fireMap[i][j]=1;
						
				}
			}
			int caseCnt = bfs(map, start,x,y);
			if(caseCnt==0){
				sb.append("IMPOSSIBLE").append("\n");
			}else 
				sb.append(caseCnt).append("\n");
			
		}
		System.out.println(sb.toString());
	}
	public static int bfs(char[][] map , Point start,int x,int y){
		int cnt =0;
		Queue<Point> queue = new LinkedList<Point>();
		queue.offer(start);
		isVisited[start.x][start.y]=1;
		int time=1 ;
		
		while(!queue.isEmpty()){
			
			
			Point current = queue.poll();
		//	System.out.println("현재위치 " +current.x +"," +current.y + isVisited[current.x][current.y]);
			
			if(current.x ==0 || current.y ==0|| current.x == x-1 ||current.y== y-1){
				return time  ;
			}
			if(isVisited[current.x][current.y]==time){
			//	System.out.println("시간 "+time);
				
				// 시간당 불 번짐 
				boolean moreFire=false;
				for(int i =0; i <x; i++){
					for(int j =0; j <y; j++){
						
						// 지금 시간에 번진 불만을 검사
						if(fireMap[i][j]==time){
							
							for(int[] direction :DIRECTIONS ){
								int fireNextX = i + direction[0];
								int fireNextY = j + direction[1];
								// 범위안에 있으면서 
								if(0<=fireNextX && fireNextX<x && 0<=fireNextY && fireNextY<y){
									// 현재 상태가 . @ 이고 현재 방문한 
									if((map[fireNextX][fireNextY]=='.'||map[fireNextX][fireNextY]=='@' ) && isVisited[fireNextX][fireNextY]!=time+1 && fireMap[fireNextX][fireNextY]==0){
										// 맵 업데이트 , fireMap 을 시간으로 업데이트 
										map[fireNextX][fireNextY]='*';
										
										fireMap[fireNextX][fireNextY] = time+1;
									}
								}
							}
							
						}
					}
				}
				/*for(int i =0; i <x; i++){
					System.out.println();
					for(int j =0; j <y; j++){
						System.out.print(map[i][j]);
						
					}
				}*/
				
				time+=1;
				
			}
			for(int[] direction :DIRECTIONS ){
				int nextX = current.x + direction[0];
				int nextY = current.y + direction[1];
				
				if(0<=nextX && nextX<x && 0<=nextY && nextY<y){
					if(map[nextX][nextY]=='.' && isVisited[nextX][nextY]==0){
						queue.offer(new Point(nextX,nextY));
					//	System.out.println("offer"+nextX +","+nextY);
						isVisited[nextX][nextY]=isVisited[current.x][current.y]+1;
						
					}
				}
			}
			
			
		}
		return 0;
		
	}
	static class Point{
		int x ;
		int y ;
		public Point(int x, int y){
			this.x = x;
			this.y = y;
		}
	}

}

sgchoi5 6년 전 0

불이 한 개만 있는게 아니고 여러 개 있을 수 있습니다.

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

문제

문제

출처

ICPC

시간초과나는이유가 뭘까

yeeeah_j 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말