알파벳

https://www.acmicpc.net/problem/1987

풀이

상하좌우를 탐색하면서 이전에 방문하지 않았던 알파벳이면 방문을 하고 아니면 재귀를 빠져나오는 식으로 구현했다.

처음에는 스택에 방문한 알파벳을 저장하고 스택에서 해당 알파벳이 있는지 검사하는 방식이었는데 이 방법은 스택에서 알파벳 유무를 검사하는데 O(n)이 든다는 점을 간과하여 시간초과를 받았다.

그래서 검사하는 부분을 수정해야했는데 알파벳은 총 26자이기때문에 boolean 배열로 해결할 수 있겠다 싶어 이 부분을 수정했다.

다행히 시간초과는 해결을 했지만 반대로 반례가 있어 틀렸습니다를 받았다.

반례는

1 2
AB

와 같이 모든 알파벳이 다른 경우다.

이 예시도 포함하도록 수정했더니 정답을 찾을 수 있었다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {
	static int r, c;
	static char[][] map;
	static int ans = 0;
	static Stack<Character> stack;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static boolean[][] visit;
	static boolean[] alpha;

	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));
		String[] in = br.readLine().split(" ");
		r = Integer.parseInt(in[0]);
		c = Integer.parseInt(in[1]);

		map = new char[r][c];
		visit = new boolean[r][c];
		alpha = new boolean[26];

		for (int i = 0; i < r; i++) {
			map[i] = br.readLine().toCharArray();
		}
		dfs(0, 0, 1);
		bw.write(ans + "\n");
		bw.flush();
		br.close();
		bw.close();
	}

	private static void dfs(int x, int y, int cnt) {
		if (!alpha[map[x][y] - 'A']) {
			alpha[map[x][y] - 'A'] = true;
			visit[x][y] = true;
			for (int i = 0; i < 4; i++) {
				if ((x + dx[i] >= 0 && x + dx[i] < r) && (y + dy[i] >= 0 && y + dy[i] < c)) {
					if (!visit[x + dx[i]][y + dy[i]]) {
						visit[x + dx[i]][y + dy[i]] = true;
						dfs(x + dx[i], y + dy[i], cnt + 1);
						visit[x + dx[i]][y + dy[i]] = false;
					}
				}
			}
			ans = Math.max(cnt, ans);
			alpha[map[x][y] - 'A'] = false;
		} else {
			ans = Math.max(ans, cnt - 1);
			return;
		}
	}
}