[백준 1987] 알파벳

📍 문제

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

 

📍 문제 풀이

같은 알파벳은 두 번이상 지날 수 없다는 조건으로 `visited` 배열을 선언했다. 

A부터 Z까지를 인덱스로 생각해 배열의 크기를 26두고 방문 처리를 해줬다.

 

dfs를 좌표와 현재까지 방문한 칸수로 재귀호출을 진행했다. 

상하좌우의 좌표를 `dx` 와 `dy`를 통해 이동하도록 하고, 해당 좌표의 값이 보드의 범위 내에 존재한다면 방문 처리해줬다.

그리고 호출이 종료된다면 다시 방문값을 false로 바꿔주면서 매번 최대값을 갱신해줬다.

 

기본적인 dfs방식과 백트래킹이 합쳐진 문제였다.

보통의 백트래킹 문제는 종료 조건이 존재하지만, 이 문제의 경우에는 종료하는 위치도, 조건도 없었다.

그렇기 때문에 매번 최대값을 갱신해주는 방법을 택했다.

 

 

📍전체코드

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

public class Main {
	static int R,C;
	static char[][] board;
	static boolean[] visited;	// 알파벳 방문 여부 확인
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 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());
		board = new char[R][C];

		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				board[i][j] = str.charAt(j);
			}
		}

		visited = new boolean[26];

		// 좌측 상단칸 방문처리
		visited[board[0][0] - 65] = true;
		answer++;

		dfs(0, 0, 1);
		System.out.println(answer);

	}

	private static void dfs(int x, int y, int result){
		answer = Integer.max(answer, result);

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

			if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
				char nc = board[nx][ny];

				// 방문하지 않았다면 방문처리
				if(!visited[nc - 65]){
					visited[nc - 65] = true;
					dfs(nx, ny, result + 1);
					visited[nc - 65] = false;
				}
			}
		}
	}
}