👀 문제 설명
세로 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
✍🏻풀이
백트래킹을 사용해서 문제를 풀었다.
visit 메서드는 재귀 함수이고, 이 메서드를 사용해 위치를 옮겨준다.
이 때, visit 메서드의 매개변수는 int x, int y, int visitCnt, Set<Character> check인데, x와 y는 현재 좌표의 위치를 나타내고, visitCnt는 (1, 1)부터 (x, y)까지 몇 개의 좌표를 방문했는지를 나타낸다. check(Set)은 무슨 알파벳을 거쳐왔는지를 나타내기 위해 사용해줬다.
현재 위치인 (x, y)에서 인접한 네 곳(상, 하, 좌, 우)를 접근한다. 인접한 곳을 (nextX, nextY)라고 할 때,
(nextX, nextY)가 범위를 벗어나거나, 이미 거쳐왔던 알파벳이라면 최댓값을 갱신하고, 다음 인접한 곳으로 넘긴다.
인접한 곳으로 이동할 수 있을 경우, check에 (nextX, nextY) 자리의 알파벳을 넣어주고, 재귀를 동해 이동한다.
visit(nextX, nextY, visitCnt + 1, check)를 빠져나오면, 백트래킹을 위해 check에서 board[nextX][nextY] 자리의 알파벳을 지워준다.
코드
package boj;
// 알파벳 (https://www.acmicpc.net/problem/1987 )
import java.util.*;
import java.io.*;
public class BOJ_1987 {
private static int R, C;
private static char[][] board;
private static int[] dx = { 0, 0, -1, 1 };
private static int[] dy = { 1, -1, 0, 0 };
private static int maxNum;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// input
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
board = new char[R + 1][C + 1];
for (int i = 1; i <= R; i++) {
String str = br.readLine();
for (int j = 1; j <= C; j++) {
board[i][j] = str.charAt(j - 1);
}
}
// solve
Set<Character> set = new HashSet<>();
set.add(board[1][1]);
visit(1, 1, 1, set);
bw.write(maxNum + "\n");
bw.flush();
bw.close();
}
private static void visit(int x, int y, int visitCnt, Set<Character> check) {
for (int dir = 0; dir < 4; dir++) {
int nextX = x + dx[dir];
int nextY = y + dy[dir];
// 범위를 벗어나거나, 이미 방문했던 알파벳이라면
// 최댓값을 갱신하고, 다음 인접한 곳으로 넘긴다.
if (nextX < 1 || nextX > R || nextY < 1 || nextY > C || check.contains(board[nextX][nextY])) {
maxNum = Math.max(maxNum, visitCnt); // 최댓값 갱신
continue;
}
check.add(board[nextX][nextY]);
visit(nextX, nextY, visitCnt + 1, check); // 이동
check.remove(board[nextX][nextY]);
}
}
}
'숨막히는 알고말고 > 문제 풀이' 카테고리의 다른 글
[Baekjoon] DFS와 BFS (0) | 2021.08.23 |
---|---|
[SWEA] Contact (2) | 2021.08.23 |
[Baekjoon] 스택 (0) | 2021.08.16 |
[Baekjoon] 숫자 카드 2 (0) | 2021.08.16 |
[Baekjoon] 나이순 정렬 (0) | 2021.08.16 |