프로그래머스_리코쳇 로봇_Day11

알고리즘 챌린지 11일차이다. 아무리 생각해봐도 주말엔 쉬는게 좋아서 쉬기로 했다. ㅋㅋ
귀찮아서 그런게 아니고,, 좀 더 오랜 기간 동안 챌린지를 이어나가기 위함이다. 

오늘도 프로그래머스 Level2에 분류된 BFS문제를 가져왔다. 

https://school.programmers.co.kr/learn/courses/30/lessons/169199?language=java

프로그래머스

 

기존의 BFS 로직을 사용해 문제를 풀면 쉽게 풀이할 수 있지만 문제에서 주어진 조건에 따라 조금의 추가 수정을 거치면 되는 쉬운 문제이다. 기존의 BFS 로직은 현재 위치에서 사방면 + 1하여 이동할 수 있는 경우에만 이동했다면, 
이 문제는 특정 방향으로 이동할 수 있는 거리 만큼 쭉 미끄러져 이동한다. 따라서 이동하다가 도착지점이 있다고 하더라도 도착으로 판단할 수 없다. 

쭉 미끄러진 경로의 가장 마지막에 도착지점이 있어야만 도착으로 인정된다는 뜻이다. 
도달할 수 없는 경우는 -1을 리턴한다. 

그렇다면 쭉 미끄러지는 이동은 어떻게 코드로 구현해야 할 까?

먼저 방향을 정하고, 해당 방향으로 이동할 수 있는 임의의  정수형 변수를 1로 초기화하자.
반복을 통해 해당 방향의 다음 위치가 이동할 수 없는 곳까지 이동한다. 
조건을 통해 경로의 끝 지점이 아직 방문하지 않은 곳이라면 큐에 추가해서 방문한다.

약간의 눈 아픈 인덱스 작업이 필요하지만 구현 자체가 어렵지 않기 때문에 자세한 내용은 코드의 주석을 참고하길 바란다.

 

Java

import java.util.*;
class Solution {
    String[][]map;
    Horse start;
    class Horse{
        int x, y, count;
        public Horse(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
    public int solution(String[] board) {
        int answer = -1;
        map = new String[board.length][board[0].length()];
        Queue<Horse> q = new LinkedList<>();
        boolean check[][] = new boolean[board.length][board[0].length()];
        
        for(int i=0; i<board.length; i++) {
            String [] temp = board[i].split("");
            for(int j=0; j<temp.length; j++){
                map[i][j] = temp[j];
                if(temp[j].equals("R")) {
                    //큐에 넣고, 방문 체크(무한루프 방지)
                    start = new Horse(i, j, 0);
                    q.add(start);
                    check[i][j] = true;
                }
            }
        }
        
        //탐색 시작
        while(!q.isEmpty()){
            Horse now = q.poll();
            
            //방문 예정 지점이 도착 지점이라면 현재 카운트를 리턴한다.
            if(map[now.x][now.y].equals("G")) return now.count;
            
            //up
            int up = 1; 
            while(now.x-up >= 0 && !map[now.x-up][now.y].equals("D")) {
                //위 방향 끝까지 이동
                up++;
            }
            if(!check[now.x-up+1][now.y]){
                q.add(new Horse(now.x-up+1, now.y, now.count+1));
                check[now.x-up+1][now.y] = true;
            }
            
            //down
            int down = 1;
            while(now.x+down < map.length && !map[now.x+down][now.y].equals("D")) {
                //아래 방향 끝까지 이동
                down++;
            }
            if(!check[now.x+down-1][now.y]){
                q.add(new Horse(now.x+down-1, now.y, now.count+1));
                check[now.x+down-1][now.y] = true;
            }
            
            //right
            int right = 1;
            while(now.y+right < map[0].length && !map[now.x][now.y+right].equals("D")) {
                //우측 방향 끝까지 이동
                right++;
            }
            if(!check[now.x][now.y+right-1]){
                q.add(new Horse(now.x, now.y+right-1, now.count+1));
                check[now.x][now.y+right-1] = true;
            }
            
            //left
            int left = 1;
            while(now.y-left >= 0 && !map[now.x][now.y-left].equals("D")) {
                //우측 방향 끝까지 이동
                left++;
            }
            if(!check[now.x][now.y-left+1]){
                q.add(new Horse(now.x, now.y-left+1, now.count+1));
                check[now.x][now.y-left+1] = true;
            }
        }
        
        return answer;
    }
}