글 읽기 - 타임아웃이 나는데 로직 검토 부탁 드려요.

javabank123 7년 전 0

타임아웃이 납니다.

재귀 호출로 했는데, 더 이상 줄일수 있는 방법이 있을까요?

아니면 아예 다른 로직을 써야 할까요? ㅠㅠ

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.Stack;

public class AlphabetDFS {

	static int row;
	static int col;
	static int cnt;
	static char[][] map;
	static boolean[] visit;
	static Stack<Character> stack = new Stack<>();
	static ArrayList<Integer> maxSize = new ArrayList();

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		row = sc.nextInt();
		col = sc.nextInt();
		map = new char[row + 1][col + 1]; // 변수 초기화

		sc.nextLine();

		for (int i = 1; i <= row; i++) {
			String temp = sc.nextLine();
			for (int j = 1; j <= col; j++) {
				map[i][j] = temp.charAt(j - 1);
			}
		}
//		printMap();

		stack.push(map[1][1]);
		
		dfs(1,1);
		
		Collections.sort(maxSize);
		int size = maxSize.size();
		
		System.out.println(maxSize.get(size-1));
	}

	public static void dfs(int y, int x) {

		if (x < col && !stack.contains(map[y][x + 1])) {	// 오른쪽
			stack.push(map[y][x + 1]);
			dfs(y,x + 1);
			stack.pop();
		}

		if (x > 1 && !stack.contains(map[y][x - 1])) {		// 왼쪽
			stack.push(map[y][x - 1]);
			dfs(y,x - 1);
			stack.pop();
		}

		if (y < row && !stack.contains(map[y+1][x])) {	// 아래
			stack.push(map[y+1][x]);
			dfs(y+1,x);
			stack.pop();
		}

		if (y > 1 && !stack.contains(map[y-1][x])) {	// 위
			stack.push(map[y-1][x]);
			dfs(y-1,x);
			stack.pop();
		}
		
		System.out.println(stack);
		maxSize.add(stack.size());
	}

	public static void printMap() {
		System.out.println();
		for (int i = 1; i <= row; i++) {
			for (int j = 1; j <= col; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
}

zlzmsrhak 7년 전 0

36-39, 68-69번째 줄을 확인해보면, 모든 결과물을 스택에 저장한 뒤 정렬을 하게 되고, 여기서 큰 배열을 정렬하기 때문에 시간초과가 나는 것 같습니다.

최댓값만 관리해야 시간초과가 나지 않습니다

javabank123 7년 전 0

네. 감사합니다.

비용이 많이 드는 Sort 로직 제거하고, 아래처럼 수정하니 PASS 되었습니다. ^^

int stackSize = stack.size();
if(stackSize > Answer)
Answer = stackSize;

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

문제

문제

출처

ICPC

타임아웃이 나는데 로직 검토 부탁 드려요.

javabank123 7년 전 0

zlzmsrhak 7년 전 0

javabank123 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말