[BaekJoon] 1987 알파벳

1.  문제 링크

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

2.  문제

요약

• 세로로 R칸, 가로로 C칸으로 된 표 모양의 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고 좌측 상단 칸에 말이 놓여 있습니다.
• 말은 상하좌우로 인접한 네 칸 중 한 칸으로 이동할 수 있고 새로 이동한 칸에 적혀있는 알파벳은 이전에 지나온 칸들의 알파벳과 겹치면 안됩니다.
• 좌측 상단에서 시작하여 말이 최대한 몇 칸을 지날 수 있는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 20보다 작거나 같은 R과 C가 주어지고 두 번째 줄부터 R개의 줄에는 보드에 적혀있는 C개의 대문자 알파벳들이 주어집니다.
• 출력: 첫 번째 줄에 말이 지날 수 있는 최대의 칸 수를 출력합니다.

3.  소스코드

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

public class Main {
	static char[][] map;
	static boolean[][] visited;
	ArrayList<Character> visited_char;
	int count;
	public void dfs(int x, int y) {
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		for(int i = 0; i < 4; i++) {
			int cx = x + dx[i];
			int cy = y + dy[i];
			if(cx >= 0 && cx < map.length && cy >= 0 && cy < map[0].length) {
				if(!visited[cx][cy] && !visited_char.contains(map[cx][cy])) {
					visited[cx][cy] = true;
					visited_char.add(map[cx][cy]);
					dfs(cx, cy);
					visited[cx][cy] = false;
					count = count > visited_char.size() ? count : visited_char.size();
					visited_char.remove(visited_char.size() - 1);
				}
			}
		}
	}
	
	public int getMaxSpace() {
		visited_char = new ArrayList<>();
		visited[0][0] = true;
		visited_char.add(map[0][0]);
		count = 1;
		dfs(0, 0);
		return count;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int row = Integer.parseInt(input[0]);
		int col = Integer.parseInt(input[1]);
		map = new char[row][col];
		visited = new boolean[row][col];
		for(int i = 0; i < row; i++) {
			String alphabets = br.readLine();
			for(int j = 0; j < col; j++) {
				map[i][j] = alphabets.charAt(j);
			}
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMaxSpace() + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 백트래킹 및 DFS를 이용하여 해결할 수 있습니다.
• 보드의 각 칸을 DFS를 통해 탐색하면서 이전에 방문했던 알파벳을 만난다면 바로 이전 단계로 돌아가 다른 경로를 탐색하는 문제입니다.
• 좌측 상단 칸부터 시작하여 상하좌우 칸을 확인하면서 해당 칸이 보드 안에 존재하고 아직 방문하지 않았으며 해당 칸의 알파벳이 이전에 방문하지 않은 알파벳이라면 DFS를 통해 해당 칸의 상하좌우 칸들도 마찬가지로 확인합니다.
• 그러다 만약 해당 칸이 보드 안에 존재하지 않거나 이전에 방문되었거나 해당 칸의 알파벳이 이전에 방문한 알파벳이라면 이전으로 돌아가 다른 칸을 확인합니다.

public void dfs(int x, int y) {
	int[] dx = {-1, 0, 1, 0};
	int[] dy = {0, -1, 0, 1};
	for(int i = 0; i < 4; i++) {
		int cx = x + dx[i];
		int cy = y + dy[i];
		if(cx >= 0 && cx < map.length && cy >= 0 && cy < map[0].length) {
			if(!visited[cx][cy] && !visited_char.contains(map[cx][cy])) {
				visited[cx][cy] = true;
				visited_char.add(map[cx][cy]);
				dfs(cx, cy);
				visited[cx][cy] = false;
				count = count > visited_char.size() ? count : visited_char.size();
				visited_char.remove(visited_char.size() - 1);
			}
		}
	}
}

1. 주어진 보드의 알파벳들을 2차원 배열 map에 넣고 보드와 같은 크기로 DFS 탐색 시에 해당 칸을 방문하였는지를 나타내는 2차원 배열 visited를 생성하며 DFS 탐색 시에 이전에 방문한 알파벳들을 넣기 위한 ArrayList 변수 visited_char를 생성합니다.
2. 좌측 상단 칸부터 탐색할 것이기 때문에 좌측 상단 칸에 해당하는 visited 값을 true로 변경하고 visited_char에 좌측 상단 칸의 알파벳을 넣습니다.
3. 방문한 칸의 개수를 나타내는 변수인 count를 생성하고 값을 1로 초기화합니다.
4. DFS 탐색을 통해 말이 지날 수 있는 최대의 칸 수를 구합니다.
   1. 상하좌우를 나타내는 배열 dx, dy를 생성하고 값을 초기화합니다.
   2. 탐색하고 있는 칸의 상하좌우 칸을 돌면서 말이 지날 수 있는 칸들을 찾고 그 중 최대의 칸 수를 구합니다.
      1. 탐색하려는 칸이 보드 안에 존재하고 해당 칸이 아직 방문되지 않았으며 해당 칸의 알파벳이 이전에 방문했던 알파벳이 아니라면 해당 칸을 방문하였기 때문에 해당 칸에 해당하는 visited 값을 true로 변경하고 visited_char에 해당 칸의 알파벳을 넣습니다.
      2. 재귀함수를 통해 지날 수 있는 칸들을 찾습니다.
      3. 만약 1번의 조건에 하나라도 어긋난다면 해당 칸의 visited 값을 false로 변경하고 해당 칸의 알파벳을 visited_char에서 지웁니다.
      4. 또한 이전에 방문했던 칸의 개수 중 최대 개수와 현재의 방문한 칸의 개수를 비교하여 더 긴 칸을 count의 값으로 취합니다.
5. DFS 탐색을 통해 말이 지날 수 있는 최대의 칸 수를 찾았으므로 이를 출력합니다.