[Baekjoon] 1987번 : 알파벳

1. 문제

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

• 백트래킹 문제

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

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

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

// 입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다.
(1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서
보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

// 출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

// 예제 입력 1
2 4
CAAB
ADCB

// 예제 출력 1
3

// 예제 입력 2
3 6
HFDFFB
AJHGDH
DGAGEH

// 예제 출력 2
6

// 예제 입력 3
5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

// 예제 출력 3
10

2. 핵심 아이디어

• 말은 상, 하, 좌, 우 네 가지 방향으로 이동할 수 있음
• 지금까지 지나온 모든 칸에 적혀 있는 알파벳과 다른 알파벳이 적힌 칸으로 이동해야 함
• 행의 길이(R)와 열의 길이(C)가 20 이하이므로, 백트래킹을 이용하여 모든 경우의 수 고려

3. Python 문제풀이

import sys
input = sys.stdin.readline

# 이동 좌표 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y) :
  global result
  # 동일한 경우는 한 번만 계산하기 위해 Set 자료형 사용
  q = set()
  q.add((x, y, arr[x][y]))

  while q :
    x, y, step = q.pop()
    # 가장 긴 이동 거리를 저장
    result = max(result, len(step))

    # 네 방향으로 이동하는 경우를 각각 확인
    for i in range(4) :
      nx = x + dx[i]
      ny = y + dy[i]

      # 이동할 수 있는 위치이면서, 새로운 알파벳인 경우
      if (0 <= nx and nx < r and 0 <= ny and ny < c and arr[nx][ny] not in step) :
        q.add((nx, ny, step + arr[nx][ny]))

# 전체 보드 데이터 입력 받기
r, c = map(int, input().split())
arr = []
for _ in range(r) :
  arr.append(input())

# 백트래킹 수행 결과 출력
result = 0
bfs(0, 0)
print(result)

4. Java 문제풀이

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[] visit = new boolean[26];
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int result = 0;

	public static void dfs(int x, int y, int count) {
		if (visit[arr[x][y]]) { // 0,0에 저장된 알파벳이 이미 한번 방문한 알파벳이라면,
			result = Math.max(result, count); // 정답을 갱신해준다.
			return; // 조건에 만족하므로 리턴.
		} else {
			visit[arr[x][y]] = true;
			for (int i=0; i<4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx >= 0 && ny >= 0 && nx < r && ny < c) {
					dfs(nx, ny, count + 1);
				}
			}
			visit[arr[x][y]] = false;
		}
	}

	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];

		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';
			}
		}
		dfs(0, 0, 0);
		System.out.println(result);
	}
}