Alphabet

7:45~8:16

잘한 부분 입력 크기 제한은 R,C 모두 20이고, 알파벳을 한번만 사용해야하기 때문에 입력으로 들어온 map[i][j]의 알파벳을 정수로 변환해서 A(0), B(1), C(2),....T(19) 총 20개의 알파벳의 중복을 체크하는 boolean 배열을 만들어서 DFS 탐색을 진행했다! 알파벳은 총 26개! 입력크기가 20개라고 해서 A부터 순서대로 20개의 알파벳만 사용하는 것은 경기도 오산이다!!!

map[i][j]의 알파벳 문자에서 65를 빼면 문자가 A인 경우 0, B인 경우 1, C인 경우 2,...이렇게 된다. 이미 지나친 문자라면 alpha 배열의 해당 인덱스는 true로 되있기 때문에, 다음 좌표로 이동하는 재귀함수 호출 시에 이 alpha배열의 값이 false인지 확인하고 진행해주면 된다~!

if(!alph[map[i][j]-65]) {
    dfs(nx,ny,d+1);
}

틀린 이유0 중복 방문을 체크하는 2차원 boolean 배열은 불필요하다! => 알파벳이 중복되는지 여부가 다음 좌표로 이동을 결정하는 조건이기 때문이다!

틀린 이유1⭐️⭐️⭐️⭐️⭐️ dfs 함수 리턴 타입을 정수형으로 했다. 현재 좌표가 x,y라고 하면 x,y까지 이르는 거리를 매개변수 ans로 1씩 증가하여 다음 재귀함수 호출시에 넘겨주었다. 하지만 생각해보면 이 문제에서 구하고자 하는 것은 "최단 거리"가 아니라 "최장 거리"이기 때문에 최장 거리는 7이 되었다가 8이 되었다가 한다. 현재 (x,y,8)이고 현재위치(x,y)에서 더 이동할 인접좌표가 없다면 백해야한다. 리턴되야하는 말이다. 그런데 현재의 매개변수인 ans를 리턴해버리면 이전위치 또는 원위치로 돌아가도 x,y에 이르는 거리를 뜻하는 ans는 큰 값으로 업데이트 되버려 오답으로 이르게 된다!

시뮬레이션을 해보면 1 2 3, ans = 3. 이 ans(3)값이 (0,0)원위치까지 ans로 업데이트, 리턴되서 (0,0)에 다시 왔을 때 거리값은 1부터 시작하는 게 아니라 3부터 시작하게 되고, (0,0)에서 다시 최댓값을 가지려 탐색을 하면 3 4 5, ans = 5. 이렇게 되어 ans는 3이 아닌 5가 되버린다!

그러므로 (x,y)위치에서의 거리값을 d라고 한다면, 재귀함수를 거듭호출하더라도 이 거리값은 절대 손대면 안된다! (재귀함수 호출할 때 제외하고!)

틀린 이유2 예제 1번, 2번 같은 경우는 한번에 원하는 정답을 얻을 수도 있다. 하지만 입력 크기가 커지면 커질 수록, 최댓값을 찾기 위한 탐색이 복잡해진다.

Brute Force>재귀 유형에서 x번째 숫자(문자)를 사용하여 재귀함수를 호출한뒤 리턴되고 나면 사용한 숫자(문자)를 false처리 해주는 것을 봤을 것이다. 이 문제에서도 마찬가지로, 더이상 진행할 수 없을 때까지 탐색을 진행하고 리턴될 때는 그 위치 좌표에서 boolean값을 다시 원래대로 false해주어야한다!

틀린 이유3 거리 최댓값 비교 부분 없음! 거리 최댓값은 1->2->3->4->5->6->7->8->9까지 됐다가 최댓값 갱신 부분이 없으면 9에서 작은 값으로 갱신될 수가 있다! 그러므로 꼭 꼭 최댓값으로 갱신하는 부분이 있어줘야한다!!!!!!!