leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/
해당 문제는 위 링크를 클릭하면 볼 수 있다.
문제 설명
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의 공간 복잡도가 발생한다.
'Coding_Test_C++' 카테고리의 다른 글
BaekJoon 1012번: 유기농 배추(C++ DFS/BFS) (0) | 2021.05.15 |
---|---|
BaekJoon 2667번: 단지번호붙이기(C++) (0) | 2021.05.14 |
BaekJoon 1260: DFS와 BFS (C++) (0) | 2021.05.10 |
Programmers: 더 맵게(C++) (0) | 2021.05.07 |
BaekJoon 5568번: 카드 놓기(C++) (0) | 2021.05.07 |