All :L
[BOJ/Java] 알파벳 (1987) 본문
반응형
1. 문제 분석
문제 개요
- 이 문제는
R x C크기의 보드에서 알파벳이 적힌 칸을 이동하며 최대 경로 길이를 구하는 문제이다. 각 칸에는 A부터 Z까지의 대문자 알파벳이 적혀 있으며, 한 번 방문한 알파벳이 적힌 칸은 다시 방문할 수 없다. - 출발점은 좌측 상단의
(0, 0)에서 시작하며, 상하좌우로 인접한 칸으로만 이동할 수 있다.
목표
- 중복되지 않는 알파벳을 최대한 많이 방문하면서 이동할 수 있는 경로의 최대 길이를 구하는 것이다.
입력 형식
- 첫 줄에 보드의 크기
R과C가 주어진다. - 이후
R줄에 걸쳐 각 줄마다C개의 대문자 알파벳이 주어진다.
출력 형식
- 가능한 최대 경로 길이를 출력한다.
2. 알고리즘 종류
이 문제는 "백트래킹을 이용한 깊이 우선 탐색(DFS)" 문제이다. DFS를 활용하여 경로를 탐색하고, 최대 경로 길이를 갱신한다.
3. 주요 부분 및 코드 작성 방법
1. DFS 탐색을 위한 방향 배열 설정
- 상하좌우로 이동하기 위한 방향 배열
dr과dc를 설정한다.
2. 방문 배열 및 체크 세트 초기화
visited배열을 통해 칸을 방문했는지 추적한다.checked세트를 사용하여 이미 방문한 알파벳을 기록한다.
3. DFS 구현
- 현재 위치에서 시작해 상하좌우로 이동하며 가능한 경로를 모두 탐색한다.
- 이동할 때마다 현재 위치에서 방문할 수 있는 최대 경로 길이를 갱신한다.
4. 결과 출력
- 최대 경로 길이를 출력한다.
4. 코드 설명
DFS 탐색 함수 (dfs())
public static void dfs(int r, int c, int depth) {
for (int i = 0; i < 4; i++) { // 4방향으로 탐색
int nr = r + dr[i]; // 새로운 r 좌표
int nc = c + dc[i]; // 새로운 c 좌표
if(nr < 0 || nc < 0 || nr >= R || nc >= C) continue; // 범위를 벗어난 경우 건너뜀
if(!checked.contains(board[nr][nc])) { // 아직 방문하지 않은 알파벳인 경우
checked.add(board[nr][nc]); // 해당 알파벳 추가
visited[nr][nc] = true; // 해당 위치 방문 처리
dfs(nr, nc, depth + 1); // 재귀적으로 탐색
visited[nr][nc] = false; // 백트래킹
checked.remove(board[nr][nc]); // 알파벳 제거
}
}
max = Math.max(max, depth); // 최대 경로 길이 갱신
}- 현재 위치에서 4방향으로 이동하며 DFS를 수행한다.
- 방문 가능한 경우
checked와visited에 기록하고, 재귀적으로 다음 위치로 이동한다. - 이동이 끝나면 백트래킹을 통해 상태를 복원한다.
메인 함수 (main())
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken()); // 보드의 행 크기 입력
C = Integer.parseInt(st.nextToken()); // 보드의 열 크기 입력
board = new char[R][C]; // 보드 배열 초기화
visited = new boolean[R][C]; // 방문 체크 배열 초기화
for(int i = 0; i < R; i++) board[i] = br.readLine().toCharArray(); // 보드 정보 입력
visited[0][0] = true; // 시작점 방문 처리
checked.add(board[0][0]); // 시작점 알파벳 체크
dfs(0, 0, 1); // DFS 시작
System.out.println(max); // 결과 출력
}- 보드의 크기와 알파벳 정보를 입력받아 초기화한다.
- 시작점에서 DFS를 호출하여 가능한 최대 경로 길이를 탐색한다.
- 탐색이 완료되면 최대 경로 길이를 출력한다.
5. 전체 코드
package BOJ.BOJ1987_240825;
import java.io.*;
import java.util.*;
public class Ex {
static int R, C, max = 0; // 보드 크기와 최대 경로 길이
static int[] dr = {-1, 1, 0, 0}; // 방향 벡터 (상하좌우)
static int[] dc = {0, 0, -1, 1}; // 방향 벡터 (상하좌우)
static char[][] board; // 보드 배열
static boolean[][] visited; // 방문 체크 배열
static Set<Character> checked = new HashSet<>(); // 방문한 알파벳 체크
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken()); // 보드의 행 크기 입력
C = Integer.parseInt(st.nextToken()); // 보드의 열 크기 입력
board = new char[R][C]; // 보드 배열 초기화
visited = new boolean[R][C]; // 방문 체크 배열 초기화
for(int i = 0; i < R; i++) board[i] = br.readLine().toCharArray(); // 보드 정보 입력
visited[0][0] = true; // 시작점 방문 처리
checked.add(board[0][0]); // 시작점 알파벳 체크
dfs(0, 0, 1); // DFS 시작
System.out.println(max); // 결과 출력
}
public static void dfs(int r, int c, int depth) {
for (int i = 0; i < 4; i++) { // 4방향으로 탐색
int nr = r + dr[i]; // 새로운 r 좌표
int nc = c + dc[i]; // 새로운 c 좌표
if(nr < 0 || nc < 0 || nr >= R || nc >= C) continue; // 범위를 벗어난 경우 건너뜀
if(!checked.contains(board[nr][nc])) { // 아직 방문하지 않은 알파벳인 경우
checked.add(board[nr][nc]); // 해당 알파벳 추가
visited[nr][nc] = true; // 해당 위치 방문 처리
dfs(nr, nc, depth + 1); // 재귀적으로 탐색
visited[nr][nc] = false; // 백트래킹
checked.remove(board[nr][nc]); // 알파벳 제거
}
}
max = Math.max(max, depth); // 최대 경로 길이 갱신
}
}6. 시간 초과
시간 초과 코드
package BOJ.BOJ1987_240825;
import java.io.*;
import java.util.*;
public class Main {
static int R, C, max = 0;
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
static String[][] board;
static boolean[][] visited;
static List<String> checked = new ArrayList<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
board = new String[R][C];
visited = new boolean[R][C];
for(int i = 0; i < R; i++) board[i] = br.readLine().split("");
visited[0][0] = true;
checked.add(board[0][0]);
dfs(0, 0, 1);
System.out.println(max);
}
public static void dfs(int r, int c, int depth) {
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if(nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
if(!checked.contains(board[nr][nc])) {
checked.add(board[nr][nc]);
visited[nr][nc] = true;
dfs(nr, nc, depth + 1);
visited[nr][nc] = false;
checked.remove(board[nr][nc]);
}
}
max = Math.max(max, depth);
}
}
차이점
- 자료구조의 차이:
- 첫 번째 코드에서는
checked리스트를 사용하여 방문한 알파벳을 저장하고 확인한다. - 두 번째 코드에서는
checked집합(Set)을 사용하여 방문한 알파벳을 저장하고 확인한다.
- 첫 번째 코드에서는
- 탐색 효율성:
- 첫 번째 코드의
List<String> checked는 리스트를 사용하므로, 알파벳이 이미 방문했는지 확인하는 데 O(N)의 시간이 걸린다. 이는 DFS 탐색에서 각 경로마다checked.contains()를 여러 번 호출하므로, 전체 탐색 시간이 매우 길어질 수 있다. - 반면, 두 번째 코드의
Set<Character> checked는 집합을 사용하므로, 알파벳이 이미 방문했는지 확인하는 데 O(1)의 시간이 걸린다. 이는 DFS 탐색에서 훨씬 빠르게 동작하게 되어, 시간 초과 없이 문제를 해결할 수 있다.
- 첫 번째 코드의
시간 초과의 원인
해당 코드가 시간 초과가 발생하는 주된 이유는 checked.contains() 호출 시 리스트에서 중복 여부를 확인하는 데 걸리는 시간이 크다. 리스트는 순차 검색을 하기 때문에, 리스트의 크기가 커지면 커질수록 이 연산이 느려지게 된다. 이로 인해 DFS의 시간 복잡도가 증가하여, 탐색 시간이 과도하게 길어진다.
반면, 제출 코드에서는 집합(Set)을 사용하여 중복을 확인하는 연산이 매우 빠르게 이루어지므로, 동일한 탐색을 훨씬 효율적으로 수행할 수 있다.
결론
- 자료구조 선택: 리스트(List)보다 집합(Set)이 중복 확인 작업에서 훨씬 효율적이다.
- 탐색 시간 최적화: 자료구조의 선택에 따라 탐색의 시간 복잡도가 크게 달라질 수 있다.
따라서 리스트 대신 집합을 사용하면, 시간 초과 문제를 해결할 수 있을 것이다.
반응형
'CODING > BOJ' 카테고리의 다른 글
| [BOJ/Java] 괄호 (9012) (0) | 2024.08.26 |
|---|---|
| [BOJ/Java] 스택 (10828) (0) | 2024.08.26 |
| [BOJ/Java] 적록색약 (10026) (0) | 2024.08.25 |
| [BOJ/Java] 도키도키 간식드리미 (12789) (0) | 2024.08.25 |
| [BOJ/Java] 비밀번호 찾기 (17219) (0) | 2024.08.25 |
'CODING/BOJ' Related Articles
more
Comments