[Leetcode] 1631. Path With Minimum Effort

문제 요약

• 알고리즘 분류:  시뮬레이션, 이분탐색, 그래프탐색(DFS, BFS)
• 난이도: Medium
• 문제내용:
  • heights[row][col]는 셀 (row, col)의 높이를 나타낸다.
  • (0, 0) → (row, col)까지 도착해야 한다.
  • 상하좌우로 이동 할때 최대 이동할수있는 높이 차이만큼 이동할 수 있다.
  • 최소한 최대 이동할 수 있는 높이 차이만큼 구하여라
• 사이트 주소: https://leetcode.com/problems/path-with-minimum-effort/description/

문제풀이

 이번 문제에는 그래프 탐색과 이분탐색을 활용한 문제이다. 관련 내용은 밑에 글에서 확인 해보면 된다.

• 이분 탐색: https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89
• DFS: https://jih3508.tistory.com/94
• BFS: https://jih3508.tistory.com/96

문제 접근방법

  최소 아동할 수 있는 높이는 이분탐색으로 구하면 되고 (0, 0) → (row, col)까지는 BFS 탐색으로 하면 시간복잡도 안에 풀 수 있다.

 

(0, 0) → (row, col) 이동

 BFS 탐색은 아래 조건만 추가 하면 된다.

1. 방문여부
2. (현재위치 - 다음위치) 높이 차이가 최대 높이차이 보다 작을때

그리고 끝에 위치 도착했을때 참으로 반환 하고 도착 못하면 거짓으로 반환 한다.

Python

def bfs(gap):
    # 방향
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    # 방문 여부를 담기 위한 집합 포함 여부 할때 set으로 처리하는게 속도가 더 빠름
    paths = set([(0, 0)])
    queue = deque([(0, 0)])

    while(queue):
        nx, ny = queue.popleft()
        if (nx, ny) == (self.x - 1, self.y - 1):
            return True

        for k in range(4):
            fx, fy = nx + dx[k], ny + dy[k]
            if 0 <= fx < self.x and 0 <= fy < self.y and (fx, fy) not in paths and abs(self.heights[nx][ny] - self.heights[fx][fy]) <= gap:
                queue.append((fx, fy))
                paths.add((fx, fy))

    return False

 

Java

public boolean bfs(int gap) {
    Queue<int []> queue = new LinkedList<>();
    queue.add(new int[] {0, 0});

    int[] path;
    int nx, ny, fx, fy;
    boolean isMatch;
    boolean[][] visited = new boolean[this.x][this.y];
    Arrays.stream(visited).forEach(visit -> Arrays.fill(visit, false));
    visited[0][0] = true;

    while(!queue.isEmpty()) {
        path = queue.poll();
        nx = path[0];
        ny = path[1];

        if ((nx == (this.x - 1)) && (ny == (this.y - 1))){
            return true;
        }

        for(int k = 0; k < 4; k++) {
            fx = nx + this.dx[k];
            fy = ny + this.dy[k];

            if ((0 <= fx) && (fx < this.x) 
                && (0 <= fy) && (fy < this.y)
                && visited[fx][fy] == false
                && Math.abs(this.heights[fx][fy] - this.heights[nx][ny]) <= gap){
                queue.add(new int[] {fx, fy});
                visited[fx][fy] = true;
            }
        }
    }

    return false;
}

• Arrays.stream(visited).forEach(visit -> Arrays.fill(visit, false)): Arrays.fill(array [], value)은 1차원 배열 value로 꽉 채우는 것이다.
• Queue<int []> queue = new LinkedList<>(): DFS탐색을 위하여 큐를 사용 해야 한다. 자바에서 Queue class 자료구조를 제공해준다.

이분탐색

• 이분 탐색으로 최소 값을 구하기 위해서 Lower Bound 형식으로 구한다. 
• bfs 탐색으로 끝까지 도달 하면 최대 값을 줄이는 방식으로 진행하고 아니면 최소값을 늘린다.

Python

right = max(max(heights, key=lambda height: max(height)))
left = 0

while left < right:
    mid = (left + right) // 2

    # mid 안에 끝까지 갈수 있을 경우 큰 값을 줄인다.
    if bfs(mid):
        right = mid
    else:
        left = mid + 1

return right

• max(max(heights, key=lambda height: max(height)))  :  2차원 배열 중 큰 값 기준을  각 배열에서 가장 큰 값으로 나타 낸다.

Java

 문제에서 높이 최대가 1,000,000이라서 큰 값을 1,000,001로 한다.

int left = 0;
    int right = 1000001;
    int mid;

    // 이분 탐색
    while(left < right) {
        mid = (left + right) / 2;

        // mid 안에 끝까지 갈수 있을 경우 큰 값을 줄인다.
        if (bfs(mid)) {
            right = mid;
        }else {
            left = mid + 1;
        }
    }

    return right;
}

 

시간 복잡도는 이분 탐색과 DFS 탐색으로 인하여 O(N^2*logN) 정도 나온다.

Code

Python

from collections import deque

class Solution:
    def minimumEffortPath(self, heights) -> int:
        def bfs(gap):
            # 방향
            dx = [1, -1, 0, 0]
            dy = [0, 0, 1, -1]

            # 방문 여부를 담기 위한 집합 포함 여부 할때 set으로 처리하는게 속도가 더 빠름
            paths = set([(0, 0)])
            queue = deque([(0, 0)])

            while(queue):
                nx, ny = queue.popleft()
                if (nx, ny) == (self.x - 1, self.y - 1):
                    return True

                for k in range(4):
                    fx, fy = nx + dx[k], ny + dy[k]
                    if 0 <= fx < self.x and 0 <= fy < self.y and (fx, fy) not in paths and abs(self.heights[nx][ny] - self.heights[fx][fy]) <= gap:
                        queue.append((fx, fy))
                        paths.add((fx, fy))

            return False

        self.heights = heights
        self.x = len(self.heights)
        self.y = len(self.heights[0])


        right = max(max(heights, key=lambda height: max(height)))
        left = 0

        while left < right:
            mid = (left + right) // 2

            # mid 안에 끝까지 갈수 있을 경우 큰 값을 줄인다.
            if bfs(mid):
                right = mid
            else:
                left = mid + 1

        return right

Java

class Solution {
	
	int[][] heights;
	int x,y ;
	// 방향
	int[] dx = {1, -1, 0, 0};
	int[] dy = {0, 0, 1, -1};
	
    public int minimumEffortPath(int[][] heights) {
        this.heights = heights;
    	this.x = heights.length;
    	this.y = heights[0].length;
        
        int left = 0;
        int right = 1000001;
        int mid;
        
        // 이분 탐색
        while(left < right) {
        	mid = (left + right) / 2;
        	
        	// mid 안에 끝까지 갈수 있을 경우 큰 값을 줄인다.
        	if (bfs(mid)) {
        		right = mid;
        	}else {
        		left = mid + 1;
        	}
        }
               
    	return right;
    }
    
    public boolean bfs(int gap) {
    	Queue<int []> queue = new LinkedList<>();
    	queue.add(new int[] {0, 0});
    	
    	int[] path;
    	int nx, ny, fx, fy;
    	boolean isMatch;
    	boolean[][] visited = new boolean[this.x][this.y];
    	Arrays.stream(visited).forEach(visit -> Arrays.fill(visit, false));
    	visited[0][0] = true;
    	
    	while(!queue.isEmpty()) {
    		path = queue.poll();
    		nx = path[0];
    		ny = path[1];
    		
    		if ((nx == (this.x - 1)) && (ny == (this.y - 1))){
    			return true;
    		}
    		
    		for(int k = 0; k < 4; k++) {
    			fx = nx + this.dx[k];
    			fy = ny + this.dy[k];

    			if ((0 <= fx) && (fx < this.x) 
    				&& (0 <= fy) && (fy < this.y)
    				&& visited[fx][fy] == false
    				&& Math.abs(this.heights[fx][fy] - this.heights[nx][ny]) <= gap){
    				queue.add(new int[] {fx, fy});
    				visited[fx][fy] = true;
    			}
    		}
    	}
    	
    	return false;
    }

}