글 읽기 - 자바 시간 초과 질문 드립니다.

jwl2327 3년 전 0

저는 왜 이게 시간 초과가 나는지 이해가 안됩니다. 혹시 설명 해주실 분 계신가요 ... ㅜㅜ 감사합니다

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main { 
    static String[][] path;
    static int R,C,ans;

    public static void main(String[] args) throws IOException{ 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] temp = br.readLine().split(" ");
        R = Integer.parseInt(temp[0]);
        C = Integer.parseInt(temp[1]);
        path = new String[R][C];

        for(int i=0;i<R;i++){
            path[i] = br.readLine().split(""); 
        }
        // System.out.println("\n this is input => ");
        // for(int i=0;i<path.length;i++){
        //     System.out.println(Arrays.toString(path[i]));
        // }

        //to record the coordinates of each path.
        //when the pipes reach the destination, we can move the completed path to the clist
        for(int i=0;i<R;i++){
            path[0][0]="x";
            dfs(i,0);
            path[0][0]=".";
        }
        // System.out.println("this is the final path => ");
        // for(int i=0;i<path.length;i++){
        //     System.out.println(Arrays.toString(path[i]));
        // }
        bw.write(ans + "\n");
		bw.flush();
		bw.close();
		br.close();
    }
    public static Boolean dfs(int x, int y){
        // System.out.println("this is dfs loop x=" + x + " y=" + y);
        // System.out.println("current p => " + Arrays.toString(p));
        if(y==C-1){
            // System.out.println("found a path! ending current loop ... ");
            ans++;
            return true;
        }
        if(0<=x-1&&!path[x-1][y+1].equals("x")){
            //upper horizontal
            // System.out.println("next loop x-1 and y+1");
            path[x-1][y+1]="x";
            if(dfs(x-1,y+1)) return true;
            path[x-1][y+1]=".";
        }
        if(!path[x][y+1].equals("x")){
            //straight
            // System.out.println("next loop x and y+1");
            path[x][y+1]="x";
            if(dfs(x,y+1)) return true;
            path[x][y+1]=".";
        }        
        if(x+1<R&&!path[x+1][y+1].equals("x")){
            //downward horizontal
            // System.out.println("next loop x+1 and y+1");
            path[x+1][y+1]="x";
            if(dfs(x+1,y+1)) return true;
            path[x+1][y+1]=".";
        }
        return false;
    }
	
}

jwl2327 3년 전 0

해답을 찾았습니다. 노드가 막혔을 때 굳이 path[x+1][y+1]="."; 해줄 필요가 없는군요. 가장 효휼적인 길을 찾는게 문제인게 아니라서 그런거 같은데 아시는분은 알려주시면 감사하겠습니다

음 ,, 완전히 코드를 완벽히 본건 아니지만
그 지점(x+1,y+1)에 x로 표시되어 있고 끝에 도달하는데 실패했다면,( path[x+1][y+1]="." 를 수행하겠죠)
다음에 어떤 루트를 통해서라도 (x+1,y+1)에 도착했을때 (x+1,y+1) 지점에서 시작되는 경로는 무조건 끝에 도달하는데 실패하겠죠..?
근데 path[x+1][y+1]="." 를 사용한다면, 다시한번 (x+1,y+1)에서 다시 탐색이 가능하게끔 하는 구현으로 보여요.

제가 이해한 바로는 방문한지를 체크하는 visit 역할이 없어서 문제인것 같습니다.

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

문제

문제

출처

ICPC

자바 시간 초과 질문 드립니다.

jwl2327 3년 전 0

jwl2327 3년 전 0

hsw0194 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말