[백준] 1987번_알파벳_Java

문제 👉🏻 https://www.acmicpc.net/problem/1987

👀 문제 접근

---

인접한 알파벳 칸을 이동할 때, 말의 최대 이동 칸 수 구하기

• 세로 R칸, 가로 C칸으로 된 보드가 있다.
• 각 칸에는 알파벳이 하나씩 적혀있다.
• 말은 상하좌우로 인접한 네 칸 중 한 칸으로 이동할 수 있다. ⚠️ 새로 이동하는 칸의 알파벳은 지나온 알파벳들과 중복될 수 없다.
  
• 말은 좌측 상단에서 시작한다.

🔎 해결 방식

---

백트래킹을 활용하여 최대로 이동할 수 있는 거리를 얻을 수 있다.

지나온 알파벳과 중복되면 안 되기 때문에 이미 지나온 알파벳은 Set에 넣어 이동할 수 있는 칸인지 확인해야 한다.

칸 이동

• moveX와 moveY를 정의하여 상, 하, 좌, 우를 이동하도록 한다.
• 다음 이동할 좌표가 이동 가능한 좌표인지 확인한다.
  • 이동 불가능이면 다른 방향으로 이동 가능한지 계속 확인
• 이동할 칸의 알파벳이 이때까지 지나온 알파벳과 중복되는지 확인한다.

이동 가능한 좌표이고, 해당 칸의 알파벳이 중복되지 않으면 이동

최대 이동 거리 구하기

• 다음 칸을 이동할 때 dfs 함수를 호출한다.
• 이 때 파라미터로 count값에 1을 더하여 호출한다.
• dfs를 새로 호출 할 때마다 max값과 현재 count값을 비교하여 최대 이동 거리를 구한다.

💻 구현 코드

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

public class Main {
    static final int[] moveX = {1, -1, 0, 0};
    static final int[] moveY = {0, 0, 1, -1};
    static int max;

    public static void dfs(int r, int c, char[][] map, int count, int x, int y, Set<Character> visited) {
        if(max < count) max = count;

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

            if(nextX < 0 || nextY < 0 || nextX >= r || nextY >= c) continue;
            if(visited.contains(map[nextX][nextY])) continue;

            visited.add(map[nextX][nextY]);
            dfs(r, c, map, count + 1, nextX, nextY, visited);
            visited.remove(map[nextX][nextY]);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        int r = Integer.parseInt(input[0]);
        int c = Integer.parseInt(input[1]);

        char[][] map = new char[r][c];
        for (int i = 0; i < r; i++) {
            String mapInput = br.readLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = mapInput.charAt(j);
            }
        }
        Set<Character> visited = new HashSet<>();
        visited.add(map[0][0]);

        dfs(r, c, map,1, 0, 0, visited);
        System.out.println(max);
    }
}

✨ 마무리

이동한 칸의 알파벳이 중복되지 않도록 구현할 방법을 찾아내면 쉽게 풀 수 있는 문제였다.

그 방법도 Set으로 풀면될거라는 생각을 금방 해낼 수 있었다.

백트래킹 문제를 처음 풀 때 쉬운 문제였음에도 동작 원리를 제대로 알지 못해서 해결하는데 오랜 시간이 걸렸다.

해당 문제를 풀면서 백트래킹 문제풀이에 자신감이 생겼고, 동작 원리에 대한 이해도도 이전보다 높아졌음을 체감할 수 있었다.