All :L

[BOJ/Java] 알파벳 (1987) 본문

CODING/BOJ

[BOJ/Java] 알파벳 (1987)

ofijwe 2024. 8. 26. 12:31
반응형

알파벳 (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);
    }
}

차이점

  1. 자료구조의 차이:
    • 첫 번째 코드에서는 checked 리스트를 사용하여 방문한 알파벳을 저장하고 확인한다.
    • 두 번째 코드에서는 checked 집합(Set)을 사용하여 방문한 알파벳을 저장하고 확인한다.
  2. 탐색 효율성:
    • 첫 번째 코드의 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