G1978. 알파벳

문제

제출 코드

• 사용 알고리즘 : 백트래킹

• 항상 하는 실수 1) 초반에 인덱스 값 범위 체크 안해줘서 생기는 IndexOutOfBoundsException
• 항상 하는 실수 2) 입력의 최솟값이 들어올 경우에 대한 예외 미처리
• 이번 문제는 공백 없이 데이터가 붙어서 들어오는데, 습관적으로 공백으로 spilt 해서 에러
• 예제는 잘 맞는데 틀렸다고 해서, 백준 질문에 올라온 범위 최대로 하는 테케 있길래 돌려봄
  • 새로 알게 된 것 : str.replace(old, new);
    • String의 replace 메서드는 값을 반환하는거지, 해당 객체의 고유 값을 바꾸진 않는다 !!!
    • 문자열을 수정하고 싶을 경우, replace한 값을 다시 참조해줘야 한다.
  • 분명 더이상 고칠게 없다고 생각하는데도 가져온 테케를 돌리면 무한루프가 돌아가서, 이유를 찾지 못하고 한번 더 제출했더니 통과함
    • 웹상에 올라온 테케를 무작정 맹신하지 말자
    • 그래도 답이 나와야 했을건데 왜 내 코드가 무한루프 돌았을까? 아직도 모르겠다.

package gold;

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

public class G1987_alphabet {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] line = br.readLine().split(" ");
		R = Integer.parseInt(line[0]);
		C = Integer.parseInt(line[1]);

		map = new String[R][C];
		for(int r=0; r<R; r++) {
			map[r] = br.readLine().split("");
		}

		str = map[0][0];
		backTracking(0, 0);

		System.out.println(max);
	}

	static int R, C;
	static String str;
	static int max = 1;
	static String[][] map;

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

	/* 백트래킹으로 알파벳 수집하며 나아가는 메서드
	 * - i : 현재 위치의 행 인덱스
	 * - j : 현재 위치의 열 인덱스
	 */
	static void backTracking(int i, int j) {
		if(max == 26) return;
		for(int d=0; d<4; d++) {
			int ni = i + di[d];
			int nj = j + dj[d];

			if(ni<0 || ni>R-1 || nj<0 || nj>C-1 || str.contains(map[ni][nj])) continue;

			str += map[ni][nj];					// 알파벳 추가
			max = Math.max(max, str.length());

			backTracking(ni, nj);
			str = str.replace(map[ni][nj], "");	// 알파벳 삭제 (replace후 다시 변수에 값넣어줘야해)
		}
	}
}