[백준 JAVA] 20436 ZOAC 3

20436 ZOAC 3

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

문제설명

QWERTY 키보드에서 문자열을 입력하는 데 필요한 시간을 계산한다.

자음과 모음을 구분하여 각각 왼손과 오른손으로 입력한다.

문제풀이

• QWERTY 키보드에서 자음과 모음은 각각 다른 맵에 저장된다.
• 각 키는 (행, 열) 좌표로 표현되며, 키보드의 각 위치가 미리 정의되어 있다.
  
  • 프로그램은 현재 왼손과 오른손의 위치를 추적한다.
  • 입력 문자열의 각 문자에 대해:
    • 문자가 자음인지 모음인지 검사한다.
    • 현재 손의 위치에서 해당 문자의 위치까지의 거리를 계산한다.
    • 맨해튼 거리 공식을 사용하여 거리를 계산한다. 거리=∣x1−x2∣+∣y1−y2
    • 문자를 입력한 후 손의 위치를 업데이트하고, 각 문자 입력에 대해 1초를 추가한다.

 

O(N) 시간복잡도

메서드는 키보드의 레이아웃을 초기화하는데, 상수 시간 O(1)이 소요된다.

 키보드 레이아웃은 고정되어 있다.

전체코드

import java.util.*;
import java.io.*;

public class Main {
    // 3D 배열로 5x5x5 미로 정의
    static int[][][] maze = new int[5][5][5], mazeCopy = new int[5][5][5];
    // 회전 및 층 정보를 저장할 배열
    static int arr[] = new int[5], floor[] = new int[5];
    // 층 사용 여부를 체크하는 배열
    static boolean check[] = new boolean[5];
    // 최단 경로 결과를 저장할 변수
    static int result = Integer.MAX_VALUE;
    // BFS에서 사용할 카운트 배열
    static int[][][] count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 미로 정보를 입력받기
        for(int i = 0; i < 5; i++) {
            for(int j = 0; j < 5; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int l = 0; l < 5; l++) {
                    // 미로의 각 위치에 대한 값을 저장
                    maze[i][j][l] = Integer.parseInt(st.nextToken());
                }
            }
        }

        // 층 조합을 체크하여 가능한 모든 조합 탐색
        floorCheck(0);
        // 최단 경로가 발견되지 않았다면 -1 출력
        System.out.println((result == Integer.MAX_VALUE) ? -1 : result);
    }

    // 층 조합을 체크하는 메소드
    static void floorCheck(int k) {
        // 5개 층이 모두 선택되었을 때
        if(k == 5){
            // 회전 조합을 위한 백트래킹 호출
            backTracking(0);
            return;
        }

        for(int i = 0; i < 5; i++) {
            if(!check[i]) { // 사용되지 않은 층일 경우
                check[i] = true; // 층 사용 표시
                floor[k] = i; // 층 저장
                floorCheck(k + 1); // 다음 층으로 진행
                check[i] = false; // 층 사용 취소
            }
        }
    }

    // 회전 조합을 체크하는 백트래킹 메소드
    static void backTracking(int k) {
        if(k == 5) { // 5개 회전이 모두 선택되었을 때
            for(int i = 0; i < 5; i++) {
                rotation(); // 선택된 층을 회전
            }

            // 시작점과 목표점이 열려있는지 확인
            if(mazeCopy[0][0][0] == 1 && mazeCopy[4][4][4] == 1) {
                bfs(); // BFS를 통해 최단 경로 탐색

                if(count[4][4][4] != 0) { // 목표점에 도달한 경우
                    result = Math.min(result, count[4][4][4]); // 최단 경로 갱신
                    if(result == 12) { // 최단 경로가 12일 경우 즉시 종료
                        System.out.println(12);
                        System.exit(0);
                    }
                }
            }
            return;
        }

        for(int i = 1; i < 5; i++) { // 회전 종류를 선택
            arr[k] = i; // 현재 회전 저장
            backTracking(k + 1); // 다음 회전으로 진행
        }
    }

    // 선택된 층을 회전시키는 메소드
    static void rotation() {
        for(int i = 0; i < 5; i++) {
            int idx = floor[i]; // 현재 층 인덱스
            int rotationNum = arr[i]; // 현재 회전 번호
            for(int j = 0; j < 5; j++) {
                for(int l = 0; l < 5; l++) {
                    // 각 회전 방식에 따라 미로 복사
                    if(rotationNum == 1) {
                        mazeCopy[idx][j][l] = maze[i][j][l]; // 0도 회전
                    }
                    if(rotationNum == 2) {
                        mazeCopy[idx][l][4 - j] = maze[i][j][l]; // 90도 시계 방향 회전
                    }
                    if(rotationNum == 3) {
                        mazeCopy[idx][4 - j][4 - l] = maze[i][j][l]; // 180도 회전
                    }
                    if(rotationNum == 4) {
                        mazeCopy[idx][4 - l][j] = maze[i][j][l]; // 90도 반시계 방향 회전
                    }
                }
            }
        }
    }

    // BFS로 최단 경로를 찾는 메소드
    static void bfs() {
        int[][] dist = {{-1, 0, 0}, {1, 0, 0}, {0, 0, -1}, {0, 0, 1}, {0, 1, 0}, {0, -1, 0}}; // 방향 배열
        Queue<Pair> queue = new LinkedList<>(); // 큐 생성
        boolean[][][] visit = new boolean[5][5][5]; // 방문 여부 체크 배열
        count = new int[5][5][5]; // 경로 길이 저장 배열
        visit[0][0][0] = true; // 시작점 방문 처리
        queue.add(new Pair(0, 0, 0)); // 시작점 큐에 추가

        while (!queue.isEmpty()) { // 큐가 빌 때까지 반복
            Pair cur = queue.poll(); // 현재 위치 가져오기
            for(int i = 0; i < 6; i++) { // 6방향 탐색
                int nz = cur.z + dist[i][0];
                int nx = cur.x + dist[i][1];
                int ny = cur.y + dist[i][2];
                // 경계를 벗어나거나 이미 방문했거나 벽인 경우 continue
                if(nz < 0 || nz >= 5 || nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
                if(visit[nz][nx][ny] || mazeCopy[nz][nx][ny] != 1) continue;

                count[nz][nx][ny] = count[cur.z][cur.x][cur.y] + 1; // 경로 길이 증가
                if(nz == 4 && nx == 4 && ny == 4) {
                    return; // 목표점에 도달하면 종료
                }
                visit[nz][nx][ny] = true; // 방문 처리
                queue.add(new Pair(nz, nx, ny)); // 큐에 다음 위치 추가
            }
        }
    }

    // 좌표를 나타내는 Pair 클래스
    public static class Pair {
        int x; // x 좌표
        int y; // y 좌표
        int z; // z 좌표

        public Pair(int z, int x, int y) {
            this.x = x;
            this.y = y;
            this.z = z; // 생성자
        }
    }
}