문제
문제
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행, 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
입력
R C (R과 C는 모두 1보다 크거나 같고 20보다 작거나 같다)
둘째 줄부터 R번째 줄까지 C개의 대문자 알파벳들이 빈칸 없이
출력
말이 지날 수 있는 최대의 칸 수
풀이
방문 여부를 체크해야 하고, 지금 당장은 최대 길이까지 갈 수 없는 알파벳 같아 보여도 최대 길이를 재야 하므로 전체적으로 다 돌아야 한다. 그러므로 DFS를 사용해야 한다.
작성한 코드는 아래와 같다.
import java.io.*;
import java.util.*;
public class Main {
static char[][] board;
static boolean[] visited = new boolean[26];
static int dfs(int row, int col, int count) {
visited[board[row][col] - 'A'] = true;
int result = count;
if(row - 1 >= 0) {
if(!visited[board[row-1][col] - 'A']) {
result = Math.max(result, dfs(row-1, col, count+1));
}
}
if(col - 1 >= 0) {
if(!visited[board[row][col-1] - 'A']) {
result = Math.max(result, dfs(row, col-1, count+1));
}
}
if(row + 1 < board.length) {
if(!visited[board[row+1][col] - 'A']) {
result = Math.max(result, dfs(row+1, col, count+1));
}
}
if(col + 1 < board[0].length) {
if(!visited[board[row][col+1] - 'A']) {
result = Math.max(result, dfs(row, col+1, count+1));
}
}
visited[board[row][col] - 'A'] = false;
return result;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
board = new char[R][C];
for(int i=0; i<R; i++) {
String str = br.readLine();
for(int j=0; j<C; j++) {
board[i][j] = str.charAt(j);
}
}
Arrays.fill(visited, false);
bw.write(dfs(0, 0, 1) + "\n");
bw.flush();
bw.close();
br.close();
}
}문제를 풀며
처음에 count를 따로 result로 빼지 않고 그대로 사용했었는데, 값이 이상하게 나오길래 트러블슈팅하는 데에 시간을 조금 쏟았다. 그러니까 result = Math.max(result, dfs...);가 아니고 count = Math.max(count, dfs...);로 작성했었다... 뇌로 대충 시뮬레이션 하고 넘기지 말고 제대로 컴퓨터 자바의 시점에서 바라볼 것 👁 👁 ...