[Java] 백준 1987 : 알파벳

문제 링크

1.

지나왔던 알파벳인지 파악하는 부분에서 조금 헤맸던 문제.

 

list를 사용하여 전체 순회를 하게 할 수도 있지만, 시간 효율성이 떨어진다.

visited 배열을 이용하여 풀면 효율적이다.

 

 

2.

이동 거리의 최대값을 찾아야 하므로 백트래킹을 써야 한다.

그렇기 때문에 DFS를 사용하는 것이 효과적이다.

 

visited 배열은 boolean[26] 배열로 해당 알파벳 - 'A'를 한 인덱스를 이용하면 된다.

나머지는 코드를 보면 이해가 될 것이다.

 

 

3.

import java.util.Scanner;

public class Main {
    static int answer = 0, r, c;
    static char[][] data;
    static boolean[] visited = new boolean[26];

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        r = sc.nextInt();
        c = sc.nextInt();

        data = new char[r][c];
        for (int i = 0; i < r; i++) {
            String temp = sc.next();

            for (int j = 0; j < c; j++) {
                data[i][j] = temp.charAt(j);
            }
        }

        dfs(0, 0, 1);
        System.out.println(answer);
    }

    static void dfs(int x, int y, int cnt) {
        int[] dx = { 1, -1, 0, 0 };
        int[] dy = { 0, 0, 1, -1 };

        visited[data[x][y] - 'A'] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < r && 0 <= ny && ny < c) {
                if (!visited[data[nx][ny] - 'A']) {
                    dfs(nx, ny, cnt + 1);
                }
            }
        }

        visited[data[x][y] - 'A'] = false;
        answer = Math.max(answer, cnt);
    }
}

 

 

4.

 

[참고] https://geehye.github.io/baekjoon-1987/#