🦎문제

1987번 : 알파벳
LV : 골드 4

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열)에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

---

🦎풀이

핵심 아이디어 : DFS

DFS의 백트래킹을 활용해서 가능한 모든 경우의 수를 탐색하고 그 중 최댓값을 찾으면 된다.

코드 흐름

1) HashSet 생성

이미 지나온 알파벳은 다시 방문할 수 없으므로, 지나온 알파벳을 저장하는 HashSet을 생성한다.

static HashSet<Character> visited = new HashSet<>();

ArrayList가 아니라 HashSet을 사용한 이유는 배열에서 값을 추가, 삭제, 탐색하는 시간이 훨씬 짧기 때문이다.

ArrayList vs HashSet

연산	HashSet (해시 테이블)	ArrayList (배열 리스트)	비고
add (추가)	평균 O(1)	O(1)	ArrayList는 끝에 추가 시 O(1)
contains (포함 확인)	평균 O(1)	O(K) (선형 시간)	HashSet이 포함 여부 확인에 매우 빠름
remove (제거)	평균 O(1)	O(K) (선형 시간)	ArrayList는 원소를 찾고 당기는 작업 때문에 O(K)

2) dfs 함수

	private static void dfs(int x, int y, int step) {

		//최댓값 처리
		maxStep = Math.max(maxStep, step);
		// 방문처리
		visited.add(board[x][y]);

		//델타탐색을 통해 다음 값으로 이동
		for (int k = 0; k < 4; k++) {
			int nx = x + di[k];
			int ny = y + dj[k];

			//범위를 벗어나지 않고 이전에 방문한 알파벳이 아니면 이동
			if (nx >= 0 && nx < R && ny >= 0 && ny < C && !visited.contains(board[nx][ny])) {
            //재귀
				dfs(nx, ny, step + 1);
			}
		}
		// 백트래킹을 위해서 여기서 방문처리를 해제해준다.
		visited.remove(board[x][y]);

		return;
	}

---

🦎전체 코드

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

public class backjoon_alpabet_1987 {

	static int[] di = { -1, 1, 0, 0 };
	static int[] dj = { 0, 0, -1, 1 };

	static int R, C;

	static HashSet<Character> visited;
	static char[][] board;

	static int maxStep;

	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("src/input.txt"));

		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 HashSet<>();
		maxStep = 0;

		// dfs
		dfs(0, 0, 1);

		System.out.println(maxStep);
	}

	private static void dfs(int x, int y, int step) {

		// 방문처리
		maxStep = Math.max(maxStep, step);

		visited.add(board[x][y]);

		for (int k = 0; k < 4; k++) {
			int nx = x + di[k];
			int ny = y + dj[k];

			if (nx >= 0 && nx < R && ny >= 0 && ny < C && !visited.contains(board[nx][ny])) {
				dfs(nx, ny, step + 1);
			}
		}
		// 백트래킹을 위해서 여기서 방문처리를 해제해주어야 한다.
		visited.remove(board[x][y]);

		return;
	}
}