[Java] 백준 / 알파벳 / 1987번
[Java] 백준 / 알파벳 / 1987번
문제
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
3 6
HFDFFB
AJHGDH
DGAGEH
출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
6
접근 방식
dfs를 통해 1행 1열부터 4방향으로 탐색을 하며 지나온 알파벳이 아닌 알파벳으로 이동한 가장 큰 거리를 구한다
추가로 백트래킹 조건으로 다른 경로로 같은 알파벳을 가진 노드를 제외시킨다
ex )
a b
b c
위 표에서 기억자와 니은자로 c에 도착하게 되고 이는 길이가 같기 때문에 하나를 제외시켜도 된다
방법 : 비트마스킹으로 알파벳을 방문한 것을 정수형으로 관리하고 이 정수를 2차원 노드 방문 배열에 저장하여, 또 다시 해당 노드에 방문했을 시 비트마스킹한 정수와 같다면 이는 다른 경로로 같은 알파벳을 통과해온것이 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_1987_정현명 {
static int R,C;
static int cntMax;
static char matrix[][];
static int visited[][];
static int deltas[][] = {{-1,0},{0,1},{1,0},{0,-1}};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
matrix = new char[R][C];
for(int i=0;i<R;i++) {
matrix[i] = br.readLine().toCharArray();
}
cntMax = 1;
visited = new int[R][C];
dfs_backtrack(0,0,1,1<<matrix[0][0]-'A' );
System.out.println(cntMax);
}
// 2차원배열의 visited에 방문했을 때의 flag를 저장하여 다른경로로 같은 알파벳을 지나온 경우를 제외한다
public static void dfs_backtrack(int i, int j, int cnt, int flag) {
if(visited[i][j] == flag) return; // 다른 경로로 같은 알파벳을 지나왔을 때
visited[i][j] = flag;
cntMax = cntMax > cnt ? cntMax : cnt;
for(int deltaIdx = 0; deltaIdx<4; deltaIdx++) {
int nextI = i + deltas[deltaIdx][0];
int nextJ = j + deltas[deltaIdx][1];
if(nextI < 0 || nextI >= R || nextJ < 0 || nextJ >= C ) continue;
if((flag & 1<<matrix[nextI][nextJ]-'A') == 0) dfs_backtrack(nextI,nextJ,cnt+1,flag | 1<<matrix[nextI][nextJ] -'A');
}
}
}
Author And Source
이 문제에 관하여([Java] 백준 / 알파벳 / 1987번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gandi0330/Java-백준-알파벳-1987번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)