[Java] BOJ1987, 백준 - 알파벳

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

1987번: 알파벳

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256MB	56974	18078	11061	29.235%

문제

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

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

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

 

입력

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

 

출력

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

 

<풀이>

1. 왼쪽 위부터 시작해서 상, 하, 좌, 우로 일일이 이동해본다.
2. 만약 들렀던 알파벳이어서 그 지점에 들리지 못한다면 종료한다.
3. 그 지점에 들릴 수 있다면 cnt값을 1 증가시킨다.

dfs와 백트래킹을 이용해 모든 지점을 방문해주기만 하면 되는 손쉬운 문제이다.

x좌표와 y좌표를 이동할 때 반복되는 코드를 최소화하기 위해서 dx, dy 배열을 이용해  for문으로 처리해주었다.

 

import java.io.*;
import java.util.*;

public class Main {

	private static int r;
	private static int c;
	private static int max;
	private static char[][] arr;
	private static boolean[] check;

	private static int[] dx = { -1, 1, 0, 0 };
	private static int[] dy = { 0, 0, -1, 1 };

	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 char[r][c]; // 맵의 정보를 저장
		for (int i = 0; i < r; i++) {
			String s = br.readLine();
			for (int j = 0; j < c; j++) {
				arr[i][j] = s.charAt(j);
			}
		}
		check = new boolean[26]; // 지나온 알파벳인지 아닌지 저장할 배열
		max = 0;
		go(0, 0, 0);
		System.out.println(max);
	}

	private static void go(int col, int row, int cnt) {
		char ch = arr[col][row];

		// 만약 이미 들렀던 알파벳이라면 종료
		if (check[ch - 'A']) {
			// max갱신
			max = Math.max(max, cnt);
			return;
		}

		for (int i = 0; i < 4; i++) {
			int x = col + dx[i];
			int y = row + dy[i];
			if (x >= 0 && y >= 0 && x < r && y < c) {
				check[ch - 'A'] = true;
				go(x, y, cnt + 1);
				check[ch - 'A'] = false;
			}
		}
	}
}