Coding_Test_C++

LeetCode 1368번: Minimum Cost to Make at Least One Vaild Path in a Grid(C++)

leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

 

Minimum Cost to Make at Least One Valid Path in a Grid - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

해당 문제는 위 링크를 클릭하면 볼 수 있다.

 

문제 설명

1) m x n의 grid 배열이 주어진다. 해당 grid는 다음 내가 방문해야 할 cell을 가르키고 있다.

2) 각 grid의 cell은 1,2,3,4의 값을 가진다.

    - 1은 우측 화살표를 의미한다.  grid[ i ][ j ] to grid[ i ] [ j + 1 ]

    - 2는 좌측 화살표를 의미한다.  grid[ i ][ j ] to grid[ i ][ j - 1 ]

    - 3은 아래쪽 화살표를 의미한다.  grid[ i ][ j ] to grid[ i + 1 ][ j ]

    - 4는 위쪽 화살표를 의미한다.  grid[ i ][ j ] to grid[ i - 1 ][ j ]

 

3) cell이 가르키는 방향대로 따라가다간 grid 배열 밖의 index로 갈 수 도 있으니 유의해야 한다.

 

4) 도착할 수 없는 경우 화살표의 방향을 바꿀 수 있다. 화살표의 방향을 바꾸는 것은 1의 비용이 소모된다.

 

5) 화살표는 한 번에 하나만 바꿀 수 있다. 즉 같은 시간 내에 여러 개의 화살표를 바꿀 수 는 없다.

 

6) (0,0)에서 시작하여 제일 우측 하단의 배열인 (m,n)까지 갈 수 있는 최소 비용을 구해야 한다.

(최단 거리일 필요는 없다)

 

Example

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3

 

위의 그림 처럼 총 3개의 화살표를 바꾸게 되면 가장 우측하단의 cell에 도달할 수 있으니 위의 그림의 경우 return 하게 될 총 cost는 3이다.

 

풀이에서 사용한 자료구조

Deque

    - front에서는 삭제만 가능하고, rear에서는 삽입만 가능한 queue의 단점을 보완한 자료구조이다.

    - Deque는 front와 end에서 삽입과 삭제가 모두 가능하다.

    - 연속적인 메모리를 기반으로 하는 순차 컨테이너이다.

    - 원소가 존재하여 임의의 원소에 접근이 가능하다.

 

문제 풀이법

1. 화살표가 방향을 바꾼다 하여도 움직일 수 있는 방향은 상하 좌우이다.

     - vx와 vy 배열에 미리 들어갈 수 있는 상하좌우의 네 가지 조합을 넣어 준다.

int vx[4] = { 0,0,1,-1 };
int vy[4] = { 1,-1,0,0 };

2. 각 셀의 비용을 계산할 배열을 생성해 주고, 매우 큰 수로 초기화해 추후 최소 값을 비교할 때 활용한다

for (int i = 0; i < m; i++)
{
	for (int j = 0; j < n; j++)
		arr[i][j] = INF; //비용 초기화
}

3. Deque에 시작점인 (0,0)을 넣어주고, 셀의 비용의 나타내는 배열의 arr[0][0]을 0으로 초기화 한다.

 q.push_back({ 0,0 });
 arr[0][0] = 0;

4. 기존에 Queue를 쓰던 BFS 알고리즘과 Stack을 쓰던 DFS 알고리즘의 토대를 Deque을 사용하는 것으로 변형하였다.

(Queue를 사용하는 BFS나 Stack을 사용하는 DFS로 풀어도 문제에 해답을 구할 수 있으나, 더 빠른 방향으로 문제를 풀기 위하여 Deque를 사용하였다)

Deque이 빌 때 까지 아래 코드를 반복하여, 최종적으로 (m-1,n-1) 셀의 비용을 return 한다.

while (!q.empty())
{
    int x = q.front().first;
    int y = q.front().second;
    q.pop_front();


    for (int i = 0; i < 4; i++)
    {
        int tx = x + vx[i];
        int ty = y + vy[i];
        if (tx < 0 || tx >= m || ty < 0 || ty >= n)
        	continue; // grid 배열 밖으로 벗어날 경우

        int c;
        if(i!=grid[x][y]-1)
        	c=1;
        else
        	c=0;

        if (arr[tx][ty] > arr[x][y] + c)
        {
            arr[tx][ty] = arr[x][y] + c;
            if (c == 0)
            	q.push_front({ tx,ty });
            else
            	q.push_back({ tx,ty });
        }

     }

}
return arr[m - 1][n - 1];

Deque이 빌때 까지 x에 현재 deque의 가장 앞에 있는 x 값을, y에 현재 deque에 가장 앞에 있는 y 값을 담았다.

앞서 정의한 vx와 vy배열을 이용해서 갈 수 있는 방향들을 for문을 통해 확인하였으며, 원래의 grid사이즈를 벗어나는 index일 때는 continue를 활용하여 새롭게 deque에 넣지 않고 continue 시켰다.

 

현재의 grid 값과 인덱스 i 가 일치 하지 않는 경우 화살표의 방향을 바꿔야 하므로 cost를 1로 설정하였으며, 인덱스 i가 일치하는 경우 cost를 0으로 잡았다.

 

비용을 나타내는 arr의 화살표로 인해 이동할 값 (tx, ty)가 현재 위치인 (x,y) +cost 보다 크다면

값을 arr[tx][ty]=arr[x][y]+cost로 바꾸어 주었다.

 

이후 cost 값이 0인 경우 (화살표의 흐름과 내가 다음 가고자 하는 배열의 위치가 같은 경우) 계속 진행하는 것이 비용을 아낄 수 있으므로, deque의 맨 앞에 넣어서 우선순위를 가지도록 하였다.

 

반면 cost 값이 1인 경우 cost가 추가되기에, 더 나은 결과를 가지고 올 수 있는 후보들을 위해 계산을 후 순위로 미루도록 deque의 맨 뒤에 넣어주었다.

 

통합본(C++)

#include<deque>
#define INF 100001
int vx[4] = { 0,0,1,-1 };
int vy[4] = { 1,-1,0,0 };
// 1은 우측으로 (0,1) 2는 좌측으로 (0,-1) 3은 아래로 (1,0) 4는 위로(-1,0)
int arr[101][101];
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {

        int m = grid.size();// 행
        int n = grid[0].size();//열;

        deque<pair<int, int>>q;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
                arr[i][j] = INF; //비용 초기화
        }
        q.push_back({ 0,0 });
        arr[0][0] = 0;
        
        while (!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop_front();


            for (int i = 0; i < 4; i++)
            {
                int tx = x + vx[i];
                int ty = y + vy[i];
                if (tx < 0 || tx >= m || ty < 0 || ty >= n)
                    continue; // grid 배열 밖으로 벗어날 경우
                
                int c;
                if(i!=grid[x][y]-1)
                    c=1;
                else
                    c=0;
                
                if (arr[tx][ty] > arr[x][y] + c)
                {
                    arr[tx][ty] = arr[x][y] + c;
                    if (c == 0)
                        q.push_front({ tx,ty });
                    else
                        q.push_back({ tx,ty });
                }

            }

        }
        return arr[m - 1][n - 1];

    }
};

Deque을 사용했을 때 결과

Queue 사용했을 때 결과(BFS)

Stack 사용했을 때 결과(DFS) - 시간초과

 

통합본(Python3)

from collections import deque
class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        vx= [0,0,1,-1]
        vy= [1,-1,0,0]
       
        m= len(grid)
        n= len(grid[0])
        
        arr=[[0 for i in range(n)] for i in range(m)] # 2차원 배열 선언
        
        deq=deque()
        
        for i in range(m):
            for j in range(n):
                arr[i][j]=100001 #나올 수 없는 값 비용 초기화
        
        deq.append([0,0])
        arr[0][0]=0
        
        while deq:
            t=deq.popleft()
            x=t[0]
            y=t[1]
            
            for i in range (4):
                tx=x+vx[i]
                ty=y+vy[i]
                if tx<0 or tx>=m or ty<0 or ty>=n:
                    continue
                if i!= grid[x][y]-1:
                    c=1
                else:
                    c=0
                
                if arr[tx][ty]> arr[x][y]+c:
                    arr[tx][ty]=arr[x][y]+c
                    if c==0:
                        deq.appendleft([tx,ty])
                    else:
                        deq.append([tx,ty])
        
        return arr[m-1][n-1]

(풀이 방식은 위 C++과 같은 방식을 사용했습니다.)

 

통합본(JAVA)

class Solution {
    private class Pair {
        public int x, y;
        public Pair(int x, int y) { this.x = x; this.y = y; }

    }
    public int minCost(int[][] grid) {
        
        int m =grid.length;
        int n= grid[0].length;
        int[][] arr= new int[101][101];
        int[] vx={0,0,1,-1};
        int[] vy={1,-1,0,0};
        
        Deque<Pair> deq = new ArrayDeque<>();
        
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
                arr[i][j]=100001;
        }
        Pair temp= new Pair(0,0);
        deq.addLast(temp);
        arr[0][0]=0;
        
        while(deq.size()!=0)
        {
            Pair T=deq.pollFirst();
            int x=T.x;
            int y=T.y;
            
            for(int i=0; i<4; i++)
            {
                int tx=x+vx[i];
                int ty=y+vy[i];
                if (tx < 0 || tx >= m || ty < 0 || ty >= n)
                    continue; // grid 배열 밖으로 벗어날 경우
                
                int c;
                if(i!=grid[x][y]-1)
                    c=1;
                else
                    c=0;
                
                if (arr[tx][ty] > arr[x][y] + c)
                {
                    arr[tx][ty] = arr[x][y] + c;
                    Pair tmp= new Pair(tx,ty);
                    if (c == 0)
                        deq.addFirst(tmp);
                    else
                        deq.addLast(tmp);
                }

            }

        }
        return arr[m - 1][n - 1];
        
    }
}

(풀이 방식은 위 C++과 같은 방식을 사용했습니다.)

 

결론

최소 비용일 경우 먼저 계산할 수 있는 deque를 이용하여 계산한 것이 가장 빠른 알고리즘임을 알 수 있다.

시간 복잡도: O(m x n) : 한 번 계산된 cell은 다시 계산 되지 않는다.

공간 복잡도: O(m x n) : cost를 넣는 arr라는 배열의 크기를 m x n으로 만들기에 m x n의 공간 복잡도가 발생한다.