[백준 19543] 던전 지도 (JAVA)

문제

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

풀이

투포인터를 이용하여 해결할 수 있습니다.

핵심은 보스방을 갈 수 있는 범위가 있기때문에 위에서 내려오면서 범위를 계속 지정해주면서 내려가면 됩니다.

예제 1번의 경우

빨간색으로 색칠되어 있는 부분이 보스방으로 갈 수 있는 경로입니다.

투포인터를 이용하여 left는 아래 배열에서 left 인덱스부터 시작하여 왼쪽으로 이동하면서 첫번째 U 바로 뒤(배열의 끝이면 0), right는 아래 배열 right 인덱스부터 시작하여 첫번째 U(배열 끝이면 -1)로 계산합니다.

left, right를 아래 배열을 갈때마다 탐색하면 시간복잡도가 n^2이 되기 때문에 미리 계산을 해두어야 합니다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Map[] map = new Map[K];
        for (int i = 0; i < K; i++) {
            map[i] = new Map(M, br.readLine());
        }

        String input = br.readLine();
        int left = start(map[input.charAt(input.length() - 1) - 'A'].arr);
        int right = M - 1;
        long ans = right - left + 1;
        for (int i = N - 2; i >= 0; i--) {
            int num = input.charAt(i) - 'A';
            left = map[num].leftArr[left];
            right = map[num].rightArr[right];

            if (left > right) break;
            ans += right - left + 1;
        }

        System.out.println(ans);
        br.close();
    }

    public static int start(char[] arr) {
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] == 'U') return i + 1;
        }
        return 0;
    }

    public static class Map {
        char[] arr;
        int[] leftArr, rightArr;

        public Map(int M, String input) {
            arr = input.toCharArray();
            leftArr = new int[M];
            rightArr = new int[M];
            int leftIndex = 0;
            int rightIndex = -1;
            for (int i = 0; i < M; i++) {
                if (input.charAt(i) == 'U') {
                    leftArr[i] = leftIndex;
                    leftIndex = i + 1;
                    rightIndex = i;
                } else {
                    leftArr[i] = leftIndex;
                }
                rightArr[i] = rightIndex;
            }
        }
    }
}