세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
해당 알파벳일 이전에 거쳐간 적이 있는지 확인하는 부분을 포함한 DFS 문제입니다.
저는 boolean 배열으로 정보를 저장했고, index를 알파벳으로 했습니다.
예로 ‘A’일 때, A의 아스키코드인 65를 index로 이용해 boolean 배열에서 확인합니다.
boolean[] flags = new boolean[100];
char c = 'A';
flags[c] = true;
이번엔 스택이 아닌 재귀를 이용했습니다.
한 번의 재귀를 끝내고 돌아왔을 때, 이전 flags 정보 상태로 돌아가야 합니다.
flags[x] = true;
rDFS();
flags[x] = false;
이런 식으로 재귀 전에 바꾸고, 재귀 후 원복하는 형태로 원래 정보를 유지합니다.
| Method | Return | Description |
|---|---|---|
| Solution(int R, int C, char[][] arr) | - | 필요한 정보를 저장하는 생성자 |
| rDFS(int x, int y, boolean[] alCheck) | int | 재귀를 통해 DFS를 수행하는 메소드로, 최대 방문 칸 수를 반환합니다. |
| solution() | int | 초기 상태를 지정해 rDFS를 호출하는 메소드입니다. |
사용 연어: Java 11
| 메모리 | 시간 |
| 16500 KB | 1068 ms |
감사합니다.
Text by Chaelin. Photographs by Chaelin, Unsplash.