글 읽기 - 25%에서 시간초과 관련해서 질문드립니다..

enekelx1 5년 전 0

해당 지점을 들를때마다 스택안에 들른 곳의 알파벳값을 넣어줘서 다음 지점을 이동할때 내가 그동안 지나왔던 값들을 비교해서 없으면 그 지점으로 이동하는

방식으로 짰거든요.. 진행해 나가면서 모두 막힌곳이면 pop과 해당 지점의 방문기록을 원래 대로 돌려놓으면서 백트래킹하는 방식인데

시간초과가 나네요 혹시 여기에서 시간을 어떻게 줄여야하는지 힌트 좀 주신다면 감사하겠습니다!

import java.util.Iterator;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	static int R,C;
	static Stack<Character> stack = new Stack<>();
	static char[][] map;
	static boolean[][] visited;
	static int max =Integer.MIN_VALUE;
	static Iterator<Character> itr;
	
	public static void main(String[] args ) {
		Scanner scr = new Scanner(System.in);
		
		R = scr.nextInt();
		C = scr.nextInt();
		map = new char[R][C];
		visited = new boolean[R][C];
		String str;
		
		for(int i=0;i<R;i++) {
			str = scr.next();
			map[i] = str.toCharArray();
		}
		
		dfs(0,0,0);
		
		System.out.println(max);
	}
	
	public static void dfs(int y,int x,int count) {
		itr = stack.iterator();
		while(itr.hasNext()) {
			if(map[y][x] == itr.next())
				return;
		}
		//System.out.print(map[y][x]);
		stack.push(map[y][x]);
		visited[y][x] = true;
		count++;
		
		if(y+1 < R && !visited[y+1][x]) {
			dfs(y+1,x,count);
			//visited[y+1][x] = false;
		}
		
		if(y-1 >= 0 && !visited[y-1][x]) {
			dfs(y-1,x,count);
			//visited[y-1][x] = false;
		}
		
		if(x+1 < C && !visited[y][x+1]) {
			dfs(y,x+1,count);
			//visited[y][x+1] = false;
		}
		
		if(x-1 >=0 && !visited[y][x-1]) {
			dfs(y,x-1,count);
			//visited[y][x-1] = false;
		}
		stack.pop();
		visited[y][x] =false;
		
		max = Math.max(max, count);
	}
}

djm03178 5년 전 0

34~37줄을 하나의 if문으로 해결할 수 있게 만들어보세요.

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

문제

문제

출처

ICPC

25%에서 시간초과 관련해서 질문드립니다..

enekelx1 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말