[백준] | JAVA, 자바 | 1987번 - 알파벳

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

---

문제 요약 :

1. R과 C 입력받기

2. R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들을 입력받기

3. 좌측 상단 칸(1행 1열)에는 말이 놓여 있다.

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

4-1. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

5. 말이 최대한 몇 칸 지날 수 있는지 구하는 프로그램 작성

5-1. 말이 지나는 칸은 좌측 상단의 칸도 포함

---

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

// 시도 3. 메모리 15200KB, 시간 856ms
public class Main {
    private static int r, c, max;
    private static char[][] map;
    private static boolean[] check;
    public static final int[][] DELTA = {{-1,0},{1,0},{0,-1},{0,1}}; // 상, 하, 좌, 우
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 1. R과 C 입력받기
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        map = new char[r][c];

        // 2. R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들을 입력받기
        for (int i = 0; i < r; i++) {
            String line = br.readLine();
            for (int j = 0; j < line.length(); j++) {
                map[i][j] = line.charAt(j);
            }
        }

        max = 0;
        // 지나온 알파벳을 저장할 배열 생성, 좌측 상단 값을 true로 변경
        check = new boolean[26];
        // 3. 좌측 상단 칸(1행 1열)에는 말이 놓여 있다
        check[map[0][0] - 'A'] = true;

        // 5. 말이 최대한 몇 칸 지날 수 있는지 구하는 프로그램 작성
        //5-1. 말이 지나는 칸은 좌측 상단의 칸도 포함
        move(0,0, 1);

        System.out.println(max);
    }

    // 4. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다.
    private static void move(int x, int y, int cnt) {
        if (cnt > max) max = cnt;

        for (int[] delta : DELTA) {
            int nr = x + delta[0];
            int nc = y + delta[1];

            // 범위 안에 해당
            if (isRange(nr, nc)) {
                // 사용하지 않은 알파벳이라면
                if (!check[map[nr][nc] - 'A']) {
                    // true로 변경해주고 재귀 호출
                    check[map[nr][nc] - 'A'] = true;
                    move(nr, nc, cnt + 1);
                    // 원상복구
                    check[map[nr][nc] - 'A'] = false;
                }
            }
        }
    }

    private static boolean isRange(int nr, int nc) {
        return nr >= 0 && nr < r && nc >= 0 && nc < c;
    }
}

 

---

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

public class Main {
    private static int r, c, max;
    private static Character[][] map;
    private static boolean[][] visited;
    private static List<Character> check;
    public static final int[][] DELTA = {{-1,0},{1,0},{0,-1},{0,1}}; // 상, 하, 좌, 우
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        map = new Character[r][c];

        for (int i = 0; i < r; i++) {
            String line = br.readLine();
            for (int j = 0; j < line.length(); j++) {
                map[i][j] = line.charAt(j);
            }
        }

        max = 0;
        visited = new boolean[r][c];
        visited[0][0] = true;
        check = new ArrayList<>();
        check.add(map[0][0]);

        move(0,0, 1);

        System.out.println(max);

    }

    private static void move(int x, int y, int cnt) {
        if (cnt > max) max = cnt;

        for (int[] delta : DELTA) {
            int nr = x + delta[0];
            int nc = y + delta[1];

            if (isRange(nr, nc)) {
                if (!visited[nr][nc] && canMove(map[nr][nc])) {
                    visited[nr][nc] = true;
                    check.add(map[nr][nc]);
                    move(nr, nc, cnt + 1);
                    visited[nr][nc] = false;
                    check.remove(map[nr][nc]);
                }
            }
        }
    }

    private static boolean canMove(Character c) {
        return !check.contains(c);
    }

    private static boolean isRange(int nr, int nc) {
        return nr >= 0 && nr < r && nc >= 0 && nc < c;
    }
}

 

첫 번째 시도, 메모리 22276KB, 시간 4200ms

 DFS를 사용해 풀었었다.

 

public class Main {
    private static int r, c, max;
    private static Character[][] map;
    private static boolean[] check;
    public static final String ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    public static final int[][] DELTA = {{-1,0},{1,0},{0,-1},{0,1}}; // 상, 하, 좌, 우
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        map = new Character[r][c];

        for (int i = 0; i < r; i++) {
            String line = br.readLine();
            for (int j = 0; j < line.length(); j++) {
                map[i][j] = line.charAt(j);
            }
        }

        max = 0;
        // 지나온 알파벳을 저장할 배열 생성, 좌측 상단 값을 true로 변경
        check = new boolean[26];
        check[ALPHABET.indexOf(map[0][0])] = true;

        move(0,0, 1);

        System.out.println(max);
    }

    private static void move(int x, int y, int cnt) {
        if (cnt > max) max = cnt;

        for (int[] delta : DELTA) {
            int nr = x + delta[0];
            int nc = y + delta[1];

            // 범위 안에 해당
            if (isRange(nr, nc)) {
                // 사용하지 않은 알파벳이라면
                if (!check[ALPHABET.indexOf(map[nr][nc])]) {
                    // true로 변경해주고 재귀 호출
                    check[ALPHABET.indexOf(map[nr][nc])] = true;
                    move(nr, nc, cnt + 1);
                    // 원상복구
                    check[ALPHABET.indexOf(map[nr][nc])] = false;
                }
            }
        }
    }

    private static boolean isRange(int nr, int nc) {
        return nr >= 0 && nr < r && nc >= 0 && nc < c;
    }
}

 

 두 번째 시도, 메모리 16388KB, 시간 2572ms

ArrayList의 contains로 확인하던 로직을 indexOf로 변경