[백준 BOJ/Gold IV] 1987번 : 알파벳

 

https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

import java.util.*;

public class Main {
    static int R; // 세로, i
    static int C; // 가로, j
    static String[][] board;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int result = 1; // 1행 1열부터 시작하니까 무조건 한칸은 포함됨
    static Set<String> alphabet = new HashSet<>(); // 중복된건 들어가지 않음

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        board = new String[R][C];

        for (int i = 0; i < R; i++) {
            String[] str = sc.next().split("");
            for (int j = 0; j < C; j++) {
                board[i][j] = str[j];
            }
        }
        //System.out.println(Arrays.deepToString(board));

        dfs(0, 0); // 항상 1행 1열에서 시작하니까

        System.out.println(result);

    }

    static void dfs(int x, int y) {
        // 이전에 담긴 알파벳을 방문리스트에서 확인하고 없으면 진행, 있으면 끝
        // list.contains("문자")

        alphabet.add(board[x][y]);

        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if (nextX >= 0 && nextX < R && nextY>=0 && nextY < C) {
                if (!alphabet.contains(board[nextX][nextY])) {
                    dfs(nextX, nextY);
                }
            }
        }

        result = Math.max(result, alphabet.size());
        alphabet.remove(board[x][y]); // 마지막에 들어간거 제거하고 전단계로

    }
}

 

 

- 시작지점이 정해져있기 때문에 x = 0, y = 0 을 시작으로 dfs를 실행했다

- 같은 알파벳으로는 다시 가면 안되기 때문에 방문하면 HashSet에 담고 포함되어 있는지 확인하며 진행해주었다

- 지나갈 수 있는 경로가 여러가지라서 모두 확인해주기 위해 dfs를 돌고나오면 마지막에 들어간 알파벳을 제거하고 이전으로 돌아가서 새로운 경로로 다시 돌 수 있게 해줬다

- 최대로 많이 지나갈 수 있는 경로를 구하는거라서 dfs를 돌고 나오면 알파벳이 담긴 HashSet의 길이를 비교해주어 최대값이 result에 담기게 해주었다

 

 

⭐⭐

HashSet으로 바꾸기 전에는 List를 사용해주었는데 시간 초과가 나왔다

import java.util.*;

public class Main {
    // ...
    
    static List<String> alphabet = new ArrayList<>(); // 안겹치게 알파벳 담아줄 리스트

    public static void main(String[] args) {
        
    	// ....

    }

    static void dfs(int x, int y) {
        // 이전에 담긴 알파벳을 방문리스트에서 확인하고 없으면 진행, 있으면 끝
        // list.contains("문자")

        alphabet.add(board[x][y]);

        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if (nextX >= 0 && nextX < R && nextY>=0 && nextY < C) {
                if (!alphabet.contains(board[nextX][nextY])) {
                    dfs(nextX, nextY);
                }
            }
        }

        result = Math.max(result, alphabet.size());
        alphabet.remove(alphabet.size() - 1); // 리스트에서 마지막 제거하고 전단계로

    }
}

 

코드는 거의 같고 alphabet이 List이냐 HashSet이냐의 차이인데 시간초과를 줄이려고 찾아보면서 HashSet이 중복된 데이터를 찾을 때 더 효율적인 것을 알게되었다

 

List

- contains 메서드 사용 시 리스트의 모든 요소를 처음부터 끝까지 순회하며 주어진 객체와 동일한 객체가 있는지 확인

- 리스트의 크기가 커질수록 이 연산의 시간 복잡도는 O(n)으로 선형적으로 증가

 

HashSet

- contains 메서드 사용 시 요소에 대한 해시 값을 계산하여 매우 빠르게 해당 값이 있는지 확인 ( 내부적으로 해시 함수를 사용하여 요소를 저장하기 때문)

- 시간 복잡도는 일반적으로 O(1)로 상수 시간에 처리됨

 

따라서 중복된 요소를 확인할 때 HashSet이 더 효율적이기 때문에 중복 확인이 빈번하게 일어나는 경우에는 HashSet을 사용하는 것이 유리함

 

 

---

 

근데!!!!!!!!!!!!! 통과 메모리와 시간을 보니 아슬아슬하다 더 최적화된 방법을 찾고싶은데 어디를 바꿔줘야할까🤔🤔🤔

좀더 공부해보고 다시 풀어봐야겠다