글 읽기 - [Java] 같은 알고리즘인거 같은데 왜 시간초과가 뜰까요 ㅠㅠ

wistnsos 3년 전 0

상하좌우 완전 탐색 중 깬 벽의 수가 이전에 깼던 벽의 수보다 크면 무조건 탐색을 하지 않도록 바꿨는데 왜 오히려 시간초과가 나는걸까요 ㅠㅠ

import java.util.*;

public class Main {
	static int rCol;
	static int rRow;
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {1, 0, -1, 0};
	static int answer = 10000;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        rCol = sc.nextInt();
        rRow = sc.nextInt();
        sc.nextLine();
        int[][] matrix = new int[rRow][rCol];
        for(int i=0;i<rRow;i++) {
        	String line = sc.nextLine();
        	for(int j=0;j<rCol;j++) {
        		matrix[i][j] = line.charAt(j) - '0';
        	}
        }
        
        boolean[][] check = new boolean[rRow][rCol]; 
        check[0][0] = true;
        
        go(matrix, check, 0, 0, 0, rRow+rCol-2);
        
        System.out.println(answer);
    }
    
    public static void go(int[][] matrix, boolean[][] check, int row, int col, int blocks, int goal) {
    	for(int i=0;i<4;i++) {
    		if(row+col==goal) {
    			answer = answer>blocks ? blocks : answer;
    			return;
    		}
    		if(blocks>answer) {
    			return;
    		}
    		if(row+dx[i]>=0 && row+dx[i]<rRow && col+dy[i]>=0 && col+dy[i]<rCol) {
	    		if(!check[row+dx[i]][col+dy[i]]) {
	    			check[row+dx[i]][col+dy[i]] = true;
	    			if(matrix[row+dx[i]][col+dy[i]]==1) {
	    				go(matrix, check, row+dx[i], col+dy[i], blocks+1, goal);
	    			} else {
	    				go(matrix, check, row+dx[i], col+dy[i], blocks, goal);
	    			}
	    			check[row+dx[i]][col+dy[i]] = false;
	    		}
    		}
    	}
    }
}

jh05013 3년 전 0

적절히 가지치기를 하더라도 100*100은 완전탐색을 하기에 너무 큽니다.

같은 알고리즘이라는 건 무슨 뜻인가요?

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

문제

문제

출처

ICPC

[Java] 같은 알고리즘인거 같은데 왜 시간초과가 뜰까요 ㅠㅠ

wistnsos 3년 전 0

jh05013 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말