글 읽기 - BFS로 풀면 왜 시간초과가 날까요?

junu0516 3년 전 0

좀 노가다성이 짙지만 BFS로 풀었는데 시간초과가 나네요.. 혹시 왜 나는지 이유를 알려주실 수 있을까요?
package baekjoon;

import java.util.*;
import java.io.*;

public class Boj_14500 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int[][] graph = new int[n][m];
		int max = 0;
		ArrayList<int[]> maxPoints = new ArrayList<>();
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<m;j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int[] sums = new int[maxPoints.size()];
		int result = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				int[] startPoint = new int[] {i,j};
		//		System.out.println("시작지점 : "+startPoint[0]+","+startPoint[1]);
		//		System.out.println("값 : "+graph[startPoint[0]][startPoint[1]]);
				int sum = getSum(startPoint,graph,n,m);
				int extra = getSpecialSum(startPoint,graph,n,m);
				result = Math.max(sum, result);
				result = Math.max(result, extra);
			}
		}
		bw.write(result+"");
		br.close();
		bw.flush();
		bw.close();
	}
	
	public static int getSum(int[] startPoint, int[][] graph, int n, int m) {
		int sum = graph[startPoint[0]][startPoint[1]];
		int count = 1;
		Queue<int[]> toVisit = new LinkedList<int[]>();
		boolean[][]visited = new boolean[n][m];
		visited[startPoint[0]][startPoint[1]] = true;
		int[] dx = new int[] {0,0,-1,1};
		int[] dy = new int[] {-1,1,0,0};
		
		toVisit.add(startPoint);
		while(!toVisit.isEmpty()) {
			int[] currPoint = toVisit.poll();
			int currY = currPoint[0];
			int currX = currPoint[1];
			
			if(count==4) {
				break;
			}
			
			int maxY = 0;
			int maxX = 0;
			int maxValue = 0;
			for(int i=0;i<4;i++) {
				int nextY = currY + dy[i];
				int nextX = currX + dx[i];
				
				if(nextY<0 || nextX<0 || nextY>=n || nextX>=m) {
					continue;
				}
				
				if(visited[nextY][nextX] == true) {
					continue;
				}
				
				if(graph[nextY][nextX]>=maxValue) {
					maxValue = graph[nextY][nextX];
					maxY = nextY;
					maxX = nextX;
				}
			}
			
			toVisit.add(new int[] {maxY,maxX});
			visited[maxY][maxX] = true;
			count++;
			sum+= graph[maxY][maxX];
			
	//		System.out.println("다음지점 : "+maxY+","+maxX);
	//		System.out.println("값 : "+graph[maxY][maxX]);
	//		System.out.println("누적값 : "+sum);
			
		}
	//	System.out.println("final sum : "+sum);
		return sum;
	}
	public static int getSpecialSum(int[] startPoint, int[][] graph, int n, int m) {
		//ㅗ ㅜ ㅏ ㅓ 네가지 모양 검사해보기
		int y = startPoint[0];
		int x = startPoint[1];
		Queue<int[]> toVisit = new LinkedList<int[]>();
		int maxSum = 0;
		int sum = 0;
		
		//ㅗ 모양 검사
		toVisit.add(startPoint);
		toVisit.add(new int[] {y,x-1});
		toVisit.add(new int[] {y,x+1});
		toVisit.add(new int[] {y-1,x});
		while(!toVisit.isEmpty()) {
			int[] currPoint = toVisit.poll();
			int currY = currPoint[0];
			int currX = currPoint[1];
			
			if(currY<0 || currX<0 || currY>=n || currX>=m) {
				sum = 0;
				break;
			}
			
			sum += graph[currY][currX];
		}
	//	System.out.println("ㅗ : "+sum);
		maxSum = Math.max(sum, maxSum);
		sum=0;
		toVisit.clear();
		//ㅜ모양 검사
		toVisit.add(startPoint);
		toVisit.add(new int[] {y,x-1});
		toVisit.add(new int[] {y,x+1});
		toVisit.add(new int[] {y+1,x});
		while(!toVisit.isEmpty()) {
			int[] currPoint = toVisit.poll();
			int currY = currPoint[0];
			int currX = currPoint[1];
			
			if(currY<0 || currX<0 || currY>=n || currX>=m) {
				sum = 0;
				break;
			}
			
			sum += graph[currY][currX];
		}
		maxSum = Math.max(sum, maxSum);
	//	System.out.println("ㅜ : "+sum);
		sum=0;
		toVisit.clear();
		//ㅏ모양 검사
		toVisit.add(startPoint);
		toVisit.add(new int[] {y,x+1});
		toVisit.add(new int[] {y-1,x});
		toVisit.add(new int[] {y+1,x});
		while(!toVisit.isEmpty()) {
			int[] currPoint = toVisit.poll();
			int currY = currPoint[0];
			int currX = currPoint[1];
			
			if(currY<0 || currX<0 || currY>=n || currX>=m) {
				sum = 0;
				break;
			}
			sum += graph[currY][currX];
		}
		maxSum = Math.max(sum, maxSum);
	//	System.out.println("ㅏ : "+sum);
		sum=0;
		toVisit.clear();
		//ㅓ모양 검사
		toVisit.add(startPoint);
		toVisit.add(new int[] {y,x-1});
		toVisit.add(new int[] {y-1,x});
		toVisit.add(new int[] {y+1,x});
		while(!toVisit.isEmpty()) {
			int[] currPoint = toVisit.poll();
			int currY = currPoint[0];
			int currX = currPoint[1];
			if(currY<0 || currX<0 || currY>=n || currX>=m) {
				sum = 0;
				break;
			}
			sum += graph[currY][currX];
	//		System.out.println(sum);
		}
	//	System.out.println("ㅓ : "+sum);
		maxSum = Math.max(sum, maxSum);
	//	System.out.println("special case : "+maxSum);
	//	System.out.println();
		return maxSum;
	}
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

BFS로 풀면 왜 시간초과가 날까요?

junu0516 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
