백 준 - 1987

문제 : www.acmicpc.net/problem/1987

1987번: 알파벳

 

이번 포스팅에서는 백준 알고리즘에 있는 1987 문제 , 알파벳 문제에 대해서 풀어보고 과정을 정리해보도록 하겠습니다.

 

먼저 문제 내용입니다.

 

목표는 왼쪽 위 에서의 시작점에서 최대한 얼마나 이동할 수 있는지입니다. 

또한 제한 조건은 같은 알파벳의 칸으로는 이동이 불가하다는 것입니다.

 

저는 이 문제를 제귀를 이용하여서 특히 백트랙킹을 이용하서 풀었는데 그 이유는 다음과 같습니다.

문제에서 이동할 수 가 있는 경우가 4가지 (상 , 하 , 좌 , 우) 이고 이렇게 4가지 모든 방향으로 이동하면서 안되는 경우를 제거하는(중복된 알파벳으로 이동) 것으로 생각할 수 있기 때문입니다.

 

코드를 말씀드리기 앞서서 방향을 간략하게 정리하자면 아래와 같습니다.

시작을 1로 시작하면서 이동하고 나서 알파벳이 중복이 되어있는지를 검사합니다.

중복이 되었다면 해당 경우를 종료하고 움직인 칸 수를 이용해서 최대 움직인 횟수와 비교해서 갱신합니다.

단 갱신하면서 움직이고 나서 중복이 되어있는지를 검사하기 때문에 1을 빼준 값을 이용합니다.

 

전체적인 코드는 아래와 같습니다.

import java.util.*;

public class Main {

    //문제 1987

    public static int[] dx = new int[]{0 , 0, 1 , -1};
    public static int[] dy = new int[]{1 , -1, 0 , 0};

    public static int maxValue = -1;

    public static void main(String[] args) {

        Scanner stdin = new Scanner(System.in);

        int n = stdin.nextInt();
        int r = stdin.nextInt();

        char[][] arr = new char[n][r];

        stdin.nextLine();

        for(int i = 0 ; i < n ; i++) {

            String str = stdin.nextLine();

            for (int j = 0 ; j < r ; j++) {

                char ch = str.charAt(j);

                arr[i][j] = ch;
            }
        }

        int aVal = 'A' - 65;
        int zVal = 'Z' - 65;

        boolean[] flag = new boolean[zVal - aVal + 1];

        recursive(arr , 0 , 0 , flag , 1);

        System.out.println(maxValue);

    }

    public static void recursive(char[][] arr , int x , int y , boolean[] flag , int num) {

        if (flag[arr[y][x] - 65] == true) {

            maxValue = Math.max(maxValue , num-1);

            return;
        }

        for(int i = 0 ; i < 4 ; i++) {

            int newX = x + dx[i];
            int newY = y + dy[i];

            if ((newX < arr[0].length && newX >= 0 ) && (newY < arr.length && newY >= 0 )) {


                flag[arr[y][x] - 65] = true;
                recursive(arr , newX , newY , flag , num+1);

                flag[arr[y][x] - 65] = false;
            }
        }

    }



}