[프로그래머스] 2020 카카오 인턴십/키패드 누르기(자바 풀이)

 

[자바 풀이]

import java.util.*;
import java.io.*;
class Solution {
    static int[][] graph = {{1,2,3}, {4,5,6}, {7,8,9}, {-1, 0, -2}};
    static int[][] visited;
    static Queue<int[]> q;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};

    public String solution(int[] numbers, String hand) {
        StringBuilder sb = new StringBuilder(numbers.length);
        List<String> result = new ArrayList<>(); 
        int curL = -1;
        int curR = -2;

        for(int i=0; i<numbers.length; i++){
            if(numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7){ // 1, 4, 7 이면 현재 왼손의 위치로 저장
                curL = numbers[i];
                sb.append("L");
            }else if(numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9){ // 3, 6, 9 이면 현재 오른손의 위치로 저장
                curR = numbers[i];
                sb.append("R");
            }else{ // 2, 5, 8, 0 이 눌린 경우
                int leftCnt = bfs(curL, numbers[i]);
                int rightCnt = bfs(curR, numbers[i]);
                if(leftCnt < rightCnt){ // 왼손이 더 가깝다면 현재 왼손의 위치로 저장
                    curL = numbers[i];
                    sb.append("L");
                }else if(leftCnt > rightCnt){ // 오른손이 더 가깝다면 현재 오른손의 위치로 저장
                    curR = numbers[i];
                    sb.append("R");
                }else{ // 동일하면 hand변수가 왼손인지, 오른손이지 판별
                    if(hand.equals("left")){ 
                        curL = numbers[i];
                        sb.append("L");
                    }else{
                        curR = numbers[i];
                        sb.append("R");
                    }
                }
            }
        }

        return sb.toString();
    }
    static int bfs(int start, int end){
        visited = new int[4][3];
        int cnt = 0;
        q = new LinkedList<>();

        // 이중for문을 통해 입력받은 start변수(왼손 또는 오른손의 현재 위치)가 키패드에 어느 좌표에 있는지
        for(int i=0; i<4; i++){
            for(int j=0; j<3; j++){
                if(graph[i][j] == start){
                    q.offer(new int[] {i, j});
                    visited[i][j] = 1;
                } 
            }
        }
        
        while(!q.isEmpty()){
            int y = q.peek()[0];
            int x = q.peek()[1];
            q.poll();
            
            if(graph[y][x] == end){
                cnt = visited[y][x];
                break;
            }

            for(int l=0; l<4; l++){
                int yy = y + dy[l];
                int xx = x + dx[l];
                if(yy>=0 && yy <4 && xx>=0 && xx <3){
                    if(visited[yy][xx] == 0){
                        q.offer(new int[] {yy, xx});
                        visited[yy][xx] = visited[y][x] + 1;
                    }
                }
            }
        }
        return cnt-1;
    }

}

이 문제를 보고 탐색으로 풀어야겠다고 바로 생각이 든 건 아니었고 조건문만으로도 풀 수 있을 것 같았다. 하지만 도저히 생각이 안나서 BFS로 도전했던 문제

 

1. BFS를 활용해서 문제를 풀기로 정하고 보니 키패드에 대한 이차원배열을 선언해줘야 했었다. 그에 따른 방문 visited배열도 생성했다. 또 이동 상하좌우만 된다고 문제에 나와있기에 dy, dx 델타 배열도 선언했다.
2. curL, curR은 현재 왼손과 오른손의 위치를 저장해 줄 변수이고 BFS탐색을 위해서 선언했다.
3. 눌러야 하는 번호가 담긴 배열 numbers에서 순서대로 번호를 뽑아 1, 4, 7이면 무조건 curL(현재 왼손의 위치)에 저장하고 3, 6, 9는 curR(현재 오른손의 위치)에 저장했다. 
   
   
4. 번호가 2, 5, 8, 0중 하나일 경우에는 현재 손의 위치와 그 번호의 거리를 계산하는 bfs(start, end)함수를 통해 거리를 return 받는다. 그럼 leftCnt는 현재 위치한 왼손에서 눌러야 하는 번호까지의 거리가 저장된다. rightCnt 도 마찬가지
5. 거리가 저장된 leftCnt와 RightCnt를 비교해서 더 짧은 거리가 계산된 손에 눌러야 하는 번호를 저장한다. 이때 거리가 동일한 경우도 있는데 동일하면 입력받은 hand를 판별하고 그에 맞게 저장한다.