728x90
[Gold IV] 알파벳 - 1987
성능 요약
메모리: 12936 KB, 시간: 996 ms
분류
백트래킹(backtracking), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)
문제 설명
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
풀이
일반 dfs에 알파벳의 방문 여부를 추가한 문제다.
알파벳의 방문 여부를 확인하기 위해 길이가 26인 boolean 배열을 파라미터로 두고, 방문한 경우 각 알파벳에서 'A'를 뺀 값을 true로 지정하여 같은 알파벳을 다시 방문하지 않도록 하였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
static int R, C;
static char[][] map;
static int[] dr = {1, -1, 0, 0};
static int[] dc = {0, 0, 1, -1};
static boolean[][] visited;
static int ans = 0;
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());
map = new char[R][C];
visited = new boolean[R][C];
for (int i = 0; i < R; i++)
map[i] = br.readLine().toCharArray();
visited[0][0]=true;
boolean[] pick = new boolean[26];
pick[map[0][0]-'A']=true;
dfs(0, 0, pick, 1);
System.out.println(ans);
}
static void dfs(int r, int c, boolean[] pick, int cnt) {
ans = Math.max(ans,cnt);
for (int d=0; d<4; d++) {
int nr = r+dr[d];
int nc = c+dc[d];
if (nr>=0 && nr<R && nc>=0 && nc<C && !visited[nr][nc] && !pick[map[nr][nc]-'A']) {
visited[nr][nc]=true;
pick[map[nr][nc]-'A']=true;
dfs(nr, nc, pick, cnt+1);
visited[nr][nc]=false;
pick[map[nr][nc]-'A']=false;
}
}
}
}
728x90
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 1644 - 소수의 연속합 (자바 Java) (0) | 2022.10.30 |
---|---|
[백준] 1806 - 부분합 (자바 Java) (0) | 2022.10.30 |
[백준] 17143 - 낚시왕 (자바 Java) (0) | 2022.10.26 |
[백준] 12015 - 가장 긴 증가하는 부분 수열 2 (자바 Java) (0) | 2022.10.25 |
[백준] 1520 - 내리막 길 (자바 Java) (0) | 2022.10.24 |