백준 1987번 : 알파벳(Java)

 

1987번: 알파벳

---

[풀이]

 

- DFS를 이용하여 풀 수 있었습니다.
- 다음 위치를 방문할 수 있는지를 해당하는 곳의 알파벳을 이전에 방문한 적있는지 확인해야 합니다.
  - 그래서, 1차원 배열로 26개의 크기로 boolean 배열을 만들었습니다.
- 이후, 재귀적으로 메소드가 호출될 때 몇 칸을 지났는지에 대한 count 변수도 함께 넘겨줍니다.
- 최종으로는, 다음 갈 곳이 이미 방문한 곳이라 갈 수 없다면, count 변수의 최대값을 answer 변수에 담고 메소드를 종료합니다.

---

[코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int r, c;
	static int[][] arr;
	static boolean[] visited;
	static int[] dx = {0, -1, 0, 1};
	static int[] dy = {1, 0, -1, 0};
	static int answer = Integer.MIN_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());

		arr = new int[r][c];
		visited = new boolean[26];

		for (int i = 0; i < r; i++) {
			String str = br.readLine();
			for (int j = 0; j < c; j++) {
				arr[i][j] = str.charAt(j) - 'A';
			}
		}
		solve(0, 0, 0);
		System.out.println(answer);

	}

	public static void solve(int x, int y, int count) {
		if (visited[arr[x][y]]) {
			answer = Math.max(answer, count);
			return;
		}

		visited[arr[x][y]] = true;

		for (int i = 0; i < 4; i++) {
			int nextX = x + dx[i];
			int nextY = y + dy[i];

			if (nextX >= 0 && nextY >= 0 && nextX < r && nextY < c) {
				solve(nextX, nextY, count + 1);
			}
		}
		visited[arr[x][y]] = false;
	}
}