[백준][JAVA] - 알파벳(1987)

2023년 10월 26일

문제 소개

✅ 문제 제목 : 알파벳 - 골드4

🔔 문제 유형 : 백트래킹, 깊이 우선 탐색

💬 풀이 언어 : JAVA

⏱️ 풀이 시간 : 15분

🖇️ 문제 링크 : 백준 문제 링크

📝 문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

🤔 문제 분석

문제의 핵심은 “같은 알파벳이 적힌 칸을 두 번 지날 수 없다.” 라고 생각한다.

같은 알파벳이 적힌 것을 판단하는 방법은 2가지가 있을 것 같다.

HashSet을 이용한 중복 확인
크기가 26인 알파벳 배열을 이용한 중복 확인

Set을 사용해 내부 메소드를 사용하는 것보단, 배열을 이용하는 것이 메모리적 이점이 크기 때문에 배열을 선택했다.

3 6
HFDFFB
AJHGDH
DGAGEH

위와 같은 보드가 주어졌을 때, (0, 0)에서 시작해 탐색을 이어나가야 한다.

첫 탐색에서 0번 라인의 H - F - D를 탐색했다고, 다음 탐색에 해당 칸을 지날 수 없는 것이 아니라, 다시 탐색할 수 있도록 방문 상태를 false로 변경해줘야 하는 것이다.

이런 방식으로 탐색하면 최대 6칸을 이동할 수 있다.

# 탐색 방향 순서에 따라 다름
H(0, 0)
F(0, 1)
J(1, 2)
A(1, 0)
D(2, 0)
G(2, 1) 

즉, 한 탐색에서 방문한 곳을 체크하고, 해당 탐색이 끝나면 다시 방문을 취소해, 다음 탐색에서도 방문할 수 있어야하기 때문에 백트래킹을 사용하는 것이 적합하다.

😎 최종 코드

배열과 Set을 사용한 코드 결과를 확인해보면 엄청난 차이가 있다는 것을 알 수 있다.

풀이1 - 배열 사용

메모리 : 12596 KB
시간 : 1028 ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int W, H, max;
    static char[][] map;
    static int ALPHA_A = 65;
    static int[] dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1};
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        map = new char[H][W];

        // 알파벳 개수
        visited = new boolean[26];

        for (int y = 0; y < H; y++) {
            char[] charArray = br.readLine().toCharArray();
            for (int x = 0; x < W; x++) {
                map[y][x] = charArray[x];
            }
        }

        backTracking(0, 0, 1);

        System.out.println(max);

    }

    private static void backTracking(int x, int y, int cnt) {
        visited[map[y][x] - ALPHA_A] = true;

        boolean isPossible = false;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < W && ny < H) {
                if (!visited[map[ny][nx] - ALPHA_A]) {
                    isPossible = true;
                    backTracking(nx, ny, cnt + 1);
                    visited[map[ny][nx] - ALPHA_A] = false;
                }

            }
        }

        if (!isPossible) {
            max = Math.max(max, cnt);
        }

    }
}

풀이2 - Set 사용

메모리 : 296392 KB
시간 : 1896 ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static int W, H, max;
    static char[][] map;
    static int[] dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1};
    static Set<Character> set;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        map = new char[H][W];
        set = new HashSet<>();

        for (int y = 0; y < H; y++) {
            char[] charArray = br.readLine().toCharArray();
            for (int x = 0; x < W; x++) {
                map[y][x] = charArray[x];
            }
        }

        backTracking(0, 0, 1);

        System.out.println(max);

    }

    private static void backTracking(int x, int y, int cnt) {
        set.add(map[y][x]);

        boolean isPossible = false;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < W && ny < H) {
                if(!set.contains(map[ny][nx])) {
                    isPossible = true;
                    backTracking(nx, ny, cnt + 1);
                    set.remove(map[ny][nx]);
                }

            }
        }

        if (!isPossible) {
            max = Math.max(max, cnt);
        }

    }
}

Jwhy