[BFS] 문제 이름 : Reach the End in Time

문제 설명

2-D grid가 주어졌을 때 상단의 가장 왼쪽 코너에서부터 하단의 가장 오른쪽 코너까지 K초 안에 도착 가능하다면 "Yes"를, 불가능하다면 "No"를 반환해라.

막힌 곳은 '#'으로, 안막힌 곳은 '.'으로 표시된다.

시작 지점과 도착 지점은 unblocked cell이다.

상하좌우로 이동이 가능하고, 인접 cell로 이동하는데 1초가 소요된다. 

 

사용 개념

그래프 탐색, BFS

 

문제 해결 아이디어

2021.07.08 - [Algorithm/유형별 문제 풀기] - [DFS/BFS] 문제 이름 : 미로 탈출 

(위의 문제와 동일한 개념의 문제이다! 문제 내용만 다를 뿐 사실상 동일하다.)

 

주어진 문제는 시작 지점으로 부터 특정 위치(도착 지점)까지 걸리는 시간을 구하는 것이므로 탐색을 사용해야 한다. 이때 걸리는 시간을 계산하기 위해 2차원 배열의 원소값에 소요 시간이라는 가중치를 저장하면 된다. 이동 시 1초가 소요되므로, 새로 방문한 노드의 가중치 = 이전 노드의 가중치 + 1로 업데이트 시켜준다. 

 

코드

구현방식) BFS

전체 구성 : 이동 가능한 모든 노드를 탐색해 소요 시간 저장 

 

countTimeinMap() 메서드 동작 흐름 : BFS 알고리즘을 사용해 이동 가능한(unblocked) 모든 노드들을 탐색하며 가중치 증가시킨 후 도착 지점인 (N,M)의 원소값 반환(해당 위치까지 걸린 시간)

 

ㄱ) 좌표 값(x,y)을 하나의 객체에 저장하기 위해 Pair 클래스를 새로 생성하여 Queue에 Pair 객체 enqueue

ㄴ) 이동 가능한 거리에 대한(상하좌우) dx[], dy[] 리스트 생성함 

ㄷ) 좌표와 해당 좌표의 원소값이 조건을 만족하는지 검사함

    → 방문하지 않은 노드에 대해서만 가중치를 업데이트를 해줘야 하므로, 가중치 저장용 배열인 intMap[][]을 사용해 원소값이 0인 경우(처음 방문한 경우)를 판별함  

 

import java.util.*;

class Pair{ // ㄱ
    public int x;
    public int y;
    
    public Pair(int x, int y){
        this.x = x;
        this.y = y;
    }
}

class Result {

    /*
     * Complete the 'reachTheEnd' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts following parameters:
     *  1. STRING_ARRAY grid
     *  2. INTEGER maxTime
     */
    
    // ㄴ 
    public static int dx[] = {-1, 1, 0, 0}; //row (상하좌우)
    public static int dy[] = {0, 0, -1, 1}; //col (상하좌우)
    
    public static char unblocked = '.';
    public static char blocked = '#';
    
    public static int countTimeinMap(char charMap[][], int intMap[][], int x, int y) {
        //using BFS
        Queue<Pair> queue = new LinkedList<>(); //큐 생성 
        queue.offer(new Pair(x, y)); //enqueue
        
        while(!queue.isEmpty()) {
            Pair p = queue.poll(); //dequeue 
            x = p.x;
            y = p.y;
            
            //현재 위치에서 상하좌우로의 이동 위치 확인 
            for(int i = 0; i < dx.length; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // ㄷ
                //이동 위치 및 원소값이 조건을 만족하는지 확인
             	//1. Map의 범위를 벗어난 경우 
                if(nx < 0 || nx >= charMap.length || ny < 0 || ny >= charMap[0].length) continue;
                //2. 막힌 Cell인 경우 
                if(charMap[nx][ny] == blocked) continue;
                //3. 해당 Cell을 처음 방문하는 경우 
                if(intMap[nx][ny] == 0){ 
                        intMap[nx][ny] = intMap[x][y] + 1; //가중치 증가 
                        queue.offer(new Pair(nx, ny)); //enqueue 
                }    
            }
        }    
        
        //도착 지점의 소요 시간에 대한 가중치 반환 
        return intMap[charMap.length-1][charMap[0].length-1];  
    }

    public static String reachTheEnd(List<String> grid, int maxTime) {
        int rowSize = grid.size();
        int colSize = grid.get(0).length();
        
        char charMap[][] = new char[rowSize][colSize]; 
        int intMap[][] = new int[rowSize][colSize]; //가중치 저장용 배열  
        
        //charMap 채우기 (String to Int)
        for(int i = 0; i < rowSize; i++) {
            String str = grid.get(i);
            for(int j = 0; j < colSize; j++) {
                charMap[i][j] = str.charAt(j);
            }
        }
        
        if(rowSize == 1 && colSize == 1){
            if(charMap[rowSize-1][colSize-1] == unblocked) return "Yes";
            else return "No";
        }
        else{
            int time = countTimeinMap(charMap, intMap, 0,0);
            if(time != 0 && time <= maxTime) return "Yes"; //조건 만족 시 
            else return "No";
        }
    }
}