백준 1987 - 알파벳

접근

이미 방문한 알파벳을 기억하자.
경로가 막히면 되돌아가자.

추가적으로 R과 C의 크기는 최대 20.

재귀로 풀어도 문제가 없겠다!

코드 구현

전역 변수 및 초기화

static int R, C;
static char[][] letterArr;
static int[] dr = { -1, 1, 0, 0 }; // 상, 하, 좌, 우 이동
static int[] dc = { 0, 0, -1, 1 };
static int ans; // 정답(최대 이동 칸 수)을 저장할 변수

main 함수

public static void main(String[] args) throws IOException {
    // DFS 시작 전, 시작점 (0,0)의 알파벳을 Set에 추가
    Set<Character> passed = new HashSet<>();
    passed.add(letterArr[0][0]);
    // DFS 호출
    dfs(0, 0, 1, passed);
    System.out.println(ans);
}

depth의 경우 시작 칸을 포함하므로 1 부터 시작한다.

dfs 함수

public static void dfs(int r, int c, int depth, Set<Character> visited) {
    ans = Math.max(ans, depth); // 현재까지 이동한 칸 수로 ans 갱신

    for (int i = 0; i < 4; i++) {
        int newR = r + dr[i];
        int newC = c + dc[i];

        // 1. 다음 위치가 보드 범위 내에 있는지 확인
        // 2. 다음 위치의 알파벳이 이전에 방문한 적 없는지 확인
        if (newR >= 0 && newR < R && newC >= 0 && newC < C && !visited.contains(letterArr[newR][newC])) {
            // 백트래킹 과정
            visited.add(letterArr[newR][newC]); // 다음 알파벳을 방문했다고 표시
            dfs(newR, newC, depth + 1, visited); // 재귀 호출
            visited.remove(letterArr[newR][newC]); // 재귀가 끝나면 방문 표시 해제 (백트래킹)
        }
    }
}

HashSet 자체가 빨라서 문제는 없었음.

백트래킹 -> visited.remove(알파벳)을 통해,

한 경로를 깊게 탐색 후 돌아와 다른 경로를 탐색하는 “되돌리기”

정답

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 R, C;
    static char[][] letterArr;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };
    static int ans;

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

        StringTokenizer stringTk = new StringTokenizer(br.readLine());
        R = Integer.parseInt(stringTk.nextToken());
        C = Integer.parseInt(stringTk.nextToken());

        letterArr = new char[R][C];

        for (int r = 0; r < R; r++) {
            String line = br.readLine();
            for (int c = 0; c < C; c++) {
                letterArr[r][c] = line.charAt(c);
            }
        }

        Set<Character> passed = new HashSet<>();
        passed.add(letterArr[0][0]);
        dfs(0, 0, 1, passed);

        System.out.println(ans);
    }

    public static void dfs(int r, int c, int depth, Set<Character> visited) {
        ans = Math.max(ans, depth);

        for (int i = 0; i < 4; i++) {
            int newR = r + dr[i];
            int newC = c + dc[i];

            if (newR >= 0 && newR < R && newC >= 0 && newC < C && !visited.contains(letterArr[newR][newC])) {
                visited.add(letterArr[newR][newC]);
                dfs(newR, newC, depth + 1, visited);
                visited.remove(letterArr[newR][newC]);
            }
        }
    }
}

여전히 어렵다 자바!

[Java] 백준 1987 - 알파벳

여전히 친해지지 못한 자바

백준 1987 - 알파벳

접근

코드 구현

정답