[C++로 풀이] 경주로 건설 (DFS, BFS, 다익스트라)⭐⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 경주로 건설
난이도 ⭐⭐⭐
🚀 문제
🚀 내 풀이
🔥 1 차 풀이 ❌ (최소의 코너 횟수를 구해야하는걸로 착각한 풀이)
#include <string>
#include <vector>
#include <queue>
using namespace std;
struct Pos {
int x;
int y;
int corner; // (y, x) 를 방문 했을 때 여태까지의 최소 코너 횟수
Pos() { }
Pos(int _y, int _x, int _c) { y = _y; x = _x; corner = _c; }
};
struct cmp {
bool operator()(const Pos& a, const Pos& b) {
return a.corner > b.corner; // min heap
}
};
int solution(vector<vector<int>> board) {
int answer = 0;
int n = board.size();
// 시계방향 : 상->우->하->좌
int deltaY[4] = { -1, 0, 1, 0 };
int deltaX[4] = { 0, 1, 0, -1 };
vector<vector<bool>> visited(n, vector<bool>(n)); // 방문 체크
vector<vector<int>> dist(n, vector<int>(n)); // 각 정점마다 최소 횟수의 코너를 가졌을 때의 거리 (from 출발지)
vector<vector<int>> shortestCorner(n, vector<int>(n, 625)); // 각 정점마다 최소 횟수의 코너
vector<vector<Pos>> parent(n, vector<Pos>(n)); // 각 정점의 바로 윗 부모 (이전 정점)
priority_queue<Pos, vector<Pos>, cmp> pq;
/* 출발지 예약 */
pq.push(Pos(0, 0, 0));
dist[0][0] = 0;
shortestCorner[0][0] = 0;
parent[0][0] = Pos(0, 0, 0);
while (!pq.empty()) {
// 방문
Pos now = pq.top();
pq.pop();
// 다익스트라에서 필요한 과정. (정점의 최소 코너 횟수를 업데이트할 때 이미 우선순위큐에 들어있는 정점은 수정할 수가 없으므로 똑같은 정점을 또 넣는다. 최적해를 가진 똑같은 정점은 이미 방문 되었을 것이므로 이렇게 방문 체크를 해주어 똑같지만 최적해는 아닌 다른 정점을 걸러주어야 한다.)
// 더 자세한 설명은 <배달>문제 참고하기 https://ansohxxn.github.io/programmers/111/
if (visited[now.y][now.x])
continue;
visited[now.y][now.x] = true;
// 예약 (현재 방문한 정점을 기준으로한 상하좌우 4가지 방향에 대해)
for (int i = 0; i < 4; ++i) {
Pos next(now.y + deltaY[i], now.x + deltaX[i], 0); // 예약 후보 정점
if (next.y < 0 || next.y >= n || next.x < 0 || next.x >= n) // 범위를 벗어난다면 예약될 수 없는 정점
continue;
if (board[next.y][next.x] == 1) // 벽이라 갈 수 없는 곳이면 예약될 수 없는 정점
continue;
if (visited[next.y][next.x]) // 이미 방문된 정점이라면 예약될 수 없는 정점
continue;
int numOfCorner = shortestCorner[now.y][now.x]; // 현재 방문 정점까지의 최소 코너 횟수
if (now.y != 0 || now.x != 0) // 출발 정점이 아니고
if ((next.x == now.x && now.x != parent[now.y][now.x].x) || (next.y == now.y && now.y != parent[now.y][now.x].y)) // 예약 후보 정점은 자신의 부모인 현재 방문 정점과 x 혹은 y 가 같지만 현재 방문 정점은 그의 부모와 x 혹은 y 가 다르면 코너가 발생한다고 판단했다.
numOfCorner++;
if (shortestCorner[next.y][next.x] < numOfCorner) // 업뎃할 필요가 없으면 그냥 넘어감
continue;
// 업뎃하고 새롭게 예약
next.corner = numOfCorner;
pq.push(next);
dist[next.y][next.x] = dist[now.y][now.x] + 1;
shortestCorner[next.y][next.x] = numOfCorner;
parent[next.y][next.x] = now;
}
}
answer = shortestCorner[n - 1][n - 1] * 500 + dist[n - 1][n - 1] * 100;
return answer;
}
문제를 좀 더 제대로 읽을걸 너무 대충 읽었나보다.. (반성) 다익스트라로 문제를 풀긴 했는데 “코너 횟수가 최소인 경로”를 만드는 기준으로 풀이한 틀린 풀이이다. 왜 이렇게 생각을 했을까.. 😭 이렇게 풀이해놓고는 문제를 다시 읽어보고 아차 싶었다.. 코너 건설 비용이 제일 비싸므로 코너를 최소로 하는 경로도 어느정도 총 건설 비용을 최소로 하는데에 상관관계가 있을 수는 있지만 정확한 인과관계로 이어지는 것은 아니다. 이 문제는 총 건설 비용을 최소로 해야하는 문제이지 코너를 최소로 하는 경로를 구하는 문제가 아니다. 코너 횟수를 최소롷 하는 경로보다 코너 좀 여러개인 경로가 더 저렴할 수도 있는 것이다!
🔥 2 차 풀이 ⭕ (최소 “금액”이 되는 경로)
1️⃣ 다익스트라를 사용한 풀이 (우선순위큐)
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 999999
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
struct Pos { // 정점
int y, x, cost, dir; // 행, 열, 현재까지의 최소 금액, 바라보고 있는 방향
};
struct cmp {
bool operator()(const Pos& a, const Pos& b) {
return a.cost > b.cost;
}
};
int solution(vector<vector<int>> board) {
int answer = 0;
int n = board.size();
// 상하좌우
int deltaY[4] = { -1, 1, 0, 0 };
int deltaX[4] = { 0, 0, -1, 1 };
// 하나의 y, x 위치에 4 가지 바라보는 방향 저장. 하나의 위치마다 바라보는 방향별 최소 건설비용이 다를 수 있으므로!
// 2가지 정보 저장 (위치 + 바라보는 방향)
int cost[25][25][4];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int k = 0; k < 4; ++k)
cost[i][j][k] = INF; // 최소 비용을 업뎃할 것이므로 최대값으로 초기화
for (int i = 0; i < 4; ++i)
cost[0][0][i] = 0;
priority_queue<Pos, vector<Pos>, cmp> pq;
pq.push({ 0, 0, 0, -1}); // 출발지가 바라보는 방향은 UP DOWN RIGHT LEFT 어디에도 해당하지 않도록 -1 로 넘긴다. 오른쪽, 아래 두 정점 다 코너로 판단되지 않고 100이 될 수 있게.
//if (board[1][0] == 0) pq.push({ 1, 0, 100, DOWN});
//if (board[0][1] == 0) pq.push({ 0, 1, 100, RIGHT });
while (!pq.empty()) {
// 방문
Pos now = pq.top();
pq.pop();
/*
방문 체크 안해줫음 그냥 (다익스트라 굳이 방문체크 안해줘도 답 도출에 지장없다.)
근데 해주면 for문을 안들어가도 되니까 밑에 코너 계산, 비용 계산 안해도 되니까 성능상 조금은 유리하지 않을까 싶다.
if (visited[now.y][now.x][now.dir])
continue;
*/
// 예약
for (int i = 0; i < 4; ++i) {
int nextY = now.y + deltaY[i];
int nextX = now.x + deltaX[i];
int nextDir = i;
int nextCost = now.cost;
// 범위를 벗어난 곳이라면 예약 불가
if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= n || board[nextY][nextX] == 1)
continue;
// 비용 계산 (코너가 아니라면 100, 코너라면 600)
nextCost += 100;
if (now.dir == UP || now.dir == DOWN)
if (nextDir == LEFT || nextDir == RIGHT)
nextCost += 500;
if (now.dir == LEFT || now.dir == RIGHT)
if (nextDir == UP || nextDir == DOWN)
nextCost += 500;
// 🤍현재 바라보는 방향에서의 여태 구한 최소비용보다 작으면 예약🤍
if (nextCost < cost[nextY][nextX][nextDir]) {
cost[nextY][nextX][nextDir] = nextCost;
pq.push({ nextY, nextX, nextCost, nextDir });
}
}
}
// 목적지의 4 가지 방향별 최소비용 중 가장 작은 값을 선택하면 그게 바로 정답
// cost[n-1][n-1][0], cost[n-1][n-1][1], cost[n-1][n-1][2], cost[n-1][n-1][3] 중 가장 작은 것.
answer = *min_element(cost[n - 1][n - 1], cost[n - 1][n - 1] + 4);
return answer;
}
이 문제 풀이에 있어 가장 중요한 포인트
- 이미 방문한 정점이라도 재방문이 가능해야 한다.
- 왜냐하면 같은 정점이라도 바라보는 방향, 즉 어느 방향에서 왔느냐에 따라 최소 비용이 달라지기 때문이다.
- 내가 온 방향을 기억하고 있어야 한다. 👉 코너 때문에 내가 어느 방향을 바라보고 있느냐에 따라 비용이 완전히 달라지기 떄문이다.
- 방문 정점(부모)이 현재 어느 방향을 바라보고 있느냐에 따라 예약이 진행될 그 방문 정점의 4 가지 방향에 있는 자식 정점들의 비용이 결정된다.
- 방문 정점(부모)이 수평 방향을 바라보고 있다면 좌, 우 정점(자식)은 코너가 되므로 추가 비용이 +500 붙게 된다.
- 왜냐하면 내가 지금 바라보고 있는 방향에 따라 (내가 어느 방향에서 왔느냐)에 따라 "앞으로의" 최소 비용이 달라질 수 있기 때문이다.
- 즉, 하나의 정점이 바라볼 수 있는 방향은 4 가지 이니 하나의 정점마다 바라보는 방향별로 4 가지 종류의 최단 경로를 가지고 있어야 한다는 의미기도 하다.
- 방향을 저장하지 않고, 즉 방향별로 최단 경로를 업데이트하지 않고 일반 다익스트라 최단경로 구하듯이 정점 좌표가지고만 (
cost[y][x]2차원 배열만 사용하여) 각각의 정점의 최단 경로를 업뎃하면 내가 바라보는
- 방향을 저장하지 않고, 즉 방향별로 최단 경로를 업데이트하지 않고 일반 다익스트라 최단경로 구하듯이 정점 좌표가지고만 (
- 즉, 하나의 정점이 바라볼 수 있는 방향은 4 가지 이니 하나의 정점마다 바라보는 방향별로 4 가지 종류의 최단 경로를 가지고 있어야 한다는 의미기도 하다.
- 따라서 y,x 좌표뿐만아니라 내가 바라보는 방향도 저장하는 3 차원 배열을 사용해야 한다.
- 방문 정점(부모)이 현재 어느 방향을 바라보고 있느냐에 따라 예약이 진행될 그 방문 정점의 4 가지 방향에 있는 자식 정점들의 비용이 결정된다.
정점마다 바라보는 방향 4 가지 별로 최소 비용을 따로 저장해야 하는 이유 (4 가지)
현재 도로 상태가 위와 같다고 가정해보자. 노란색은 도로, 회색은 갈 수 없는 벽이다. 정점 별로 방향을 저장하지 않고 cost[y][x] 이렇게 좌표에만 최소 비용을 기록했다고 가정해보자.
- 초록색 경로를 통하여 (4, 4), (5, 4), 그리고 목적지인 (5, 5)가 각각 2100, 2700, 3300 최소 비용이 저장되어 있는 상태가 될 것이다.
- 이 상태에서 보라색 경로(바라보는 방향:👇)를 통하여 최소비용이 2300인 (4, 4) 를 예약하려고 하는데 이미 방문된 정점이고 2100 < 2300 이기 때문에 예약 되지 않는다. 즉 해당 보라색 경로는 (4, 4) 이상 진행되지 않고 (3, 4) 에서 끊겨버린다.
- 그러나! 이 보라색 경로를 따른다면 2300 - 2400 - 3000 이 되어 사실 초록 경로보다 목적지의 최소비용을 더 작은 값(3300보다 작은 3000) 으로 업데이트 할 수 있었다. 근데 일단 현재 좌표의 최소 비용만 따져서 나중에 방문할지 말지를 결정하기 때문에 보라색 경로는 (2100 < 2300)에 막혀 더 이상 진행되지 못하는 것이다.
- 이와 같은 원인은 바라보는 방향은 따지지 않고 무작정 좌표의 최소비용만 따져 비교했기 때문이다. 이 문제는 “코너”가 있기 때문에 바라보는 방향에 따라 앞으로의 비용이 완전히 바뀔 수 있다. 더 작은 비용을 발견할 수도 있다.
- 그렇기 떄문에 하나의 좌표라도 바라 보는 방향(내가 예약될 때 부모의 상하좌우 중 어디에 있었는지)이 4 가지가 있을 수 있으므로 이 좌표가 바라보고 있는 방향이 어디냐에 따라 이것과 연결된 이후 정점들의 최소 비용이 앞으로도 달라질 것이라는 것을 의미한다. 따라서 방향을
cost에 함께 3차원 배열로 저장한다!
- 그렇기 떄문에 하나의 좌표라도 바라 보는 방향(내가 예약될 때 부모의 상하좌우 중 어디에 있었는지)이 4 가지가 있을 수 있으므로 이 좌표가 바라보고 있는 방향이 어디냐에 따라 이것과 연결된 이후 정점들의 최소 비용이 앞으로도 달라질 것이라는 것을 의미한다. 따라서 방향을
이렇게 모든 정점마다 바라보고 있는 방향(= 내가 온 방향) 4 가지별로 최소비용을 저장해야 한다! 목적지는 4 가지의 방향별 최소비용 가장 최소값을 선택하면 그게 바로 정답이 될 것이다.
✈ 준비
#define INF 999999
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
struct Pos { // 정점
int y; // 행
int x; // 열
int cost; // 이 정점이 예약됐던 시점까지 최소 금액
int dir; // 이 정점이 예약됐던 시점에 바라보고 있었던 방향
};
int solution(vector<vector<int>> board) {
int answer = 0;
int n = board.size();
// 상하좌우
int deltaY[4] = { -1, 1, 0, 0 };
int deltaX[4] = { 0, 0, -1, 1 };
✈ 출발지 처리
int cost[25][25][4];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int k = 0; k < 4; ++k)
cost[i][j][k] = INF; // 최소 비용을 업뎃할 것이므로 최대값으로 초기화
for (int i = 0; i < 4; ++i) // 출발지 4 방향 0 으로 초기화
cost[0][0][i] = 0;
priority_queue<Pos, vector<Pos>, cmp> pq;
pq.push({ 0, 0, 0, -1}); // 출발지가 바라보는 방향은 UP DOWN RIGHT LEFT 어디에도 해당하지 않도록 -1 로 넘긴다. 오른쪽, 아래 두 정점 다 코너로 판단되지 않고 100이 될 수 있게.
//if (board[1][0] == 0) pq.push({ 1, 0, 100, DOWN});
//if (board[0][1] == 0) pq.push({ 0, 1, 100, RIGHT });
cost[y][x][dir]: (y, x) 정점이 dir 방향을 바라보고 있을 떄의 최소비용pq: 우선순위 큐 (정점 구조체의cost멤버가 가장 작은게 먼저 빠져나온다.)- 모든 정점은 최대값에서 시작해야 한데 (그래야 최소비용으로 업데이트가 될테니까)
- 출발지의 비용은 4 방향 모두 0 으로 초기화 한다.
- 출발지가 새로운 최소 비용으로 업데이트 되면 안되니까 가장 작은 비용으로..
✈ 예약
for (int i = 0; i < 4; ++i) {
int nextY = now.y + deltaY[i];
int nextX = now.x + deltaX[i];
int nextDir = i;
int nextCost = now.cost; // 현재 이 정점까지의 최소 비용(now 의 비용). 여기서 +100 이되거나 +600 이 되는데 예약 정점의 최소 비용이 됨
// 범위를 벗어난 곳이라면 예약 불가
if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= n || board[nextY][nextX] == 1)
continue;
// 비용 계산 (코너가 아니라면 +100, 코너라면 +600)
nextCost += 100;
if (now.dir == UP || now.dir == DOWN) // 방문 정점(부모)가 수직방향을 바라보고 있을 때
if (nextDir == LEFT || nextDir == RIGHT) // 예약 후보 정점이 수평방향을 바라보고 있다면 코너
nextCost += 500;
if (now.dir == LEFT || now.dir == RIGHT) // 방문 정점(부모)가 수평방향을 바라보고 있을 때
if (nextDir == UP || nextDir == DOWN) // 예약 후보 정점이 수직방향을 바라보고 있다면 코너
nextCost += 500;
// 🤍현재 바라보는 방향에서의 여태 구한 최소비용보다 작으면 예약🤍
if (nextCost < cost[nextY][nextX][nextDir]) {
cost[nextY][nextX][nextDir] = nextCost;
pq.push({ nextY, nextX, nextCost, nextDir });
}
}
✈ 목적지의 최소 비용
answer = *min_element(cost[n - 1][n - 1], cost[n - 1][n - 1] + 4);
목적지에 저장된 바라보는 방향 4 가지 별 최소비용 중에서 가장 작은 것을 선택하면 된다.
- *min_element(cost[n - 1][n - 1], cost[n - 1][n - 1] + 3) 처음엔 이렇게 3 으로 썼어서 틀린 부분 찾느라 얼마나 고민했는지 ㅠㅠ..
- 내 풀이가 틀린건 줄 알고 계속 뜯어고치고 고민해보고 했었는데 계속 틀렸던 이유는 이 코드에서 내가 cost[n - 1][n - 1] + 3 으로 적었기 때문이었다..
- 두 번째 파라미터는 최소값을 찾는 범위에 포함되지 않는다!!!!! \min_element(cost[n - 1][n - 1], cost[n - 1][n - 1] + 4) 이렇게 + 4 로 써야한다..
- 내 풀이가 틀린건 줄 알고 계속 뜯어고치고 고민해보고 했었는데 계속 틀렸던 이유는 이 코드에서 내가 cost[n - 1][n - 1] + 3 으로 적었기 때문이었다..
2️⃣ BFS 를 사용한 풀이 (그냥 큐)
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 999999
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
struct Pos {
int y, x, cost, dir;
};
int solution(vector<vector<int>> board) {
int answer = 0;
int n = board.size();
int deltaY[4] = { -1, 1, 0, 0 };
int deltaX[4] = { 0, 0, -1, 1 };
int cost[25][25][4];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int k = 0; k < 4; ++k)
cost[i][j][k] = INF;
for (int i = 0; i < 4; ++i)
cost[0][0][i] = 0;
queue<Pos> q;
q.push({ 0, 0, 0, -1});
//if (board[1][0] == 0) q.push({ 1, 0, 100, DOWN});
//if (board[0][1] == 0) q.push({ 0, 1, 100, RIGHT });
while (!q.empty()) {
Pos now = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int nextY = now.y + deltaY[i];
int nextX = now.x + deltaX[i];
int nextDir = i;
int nextCost = now.cost;
if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= n || board[nextY][nextX] == 1)
continue;
nextCost += 100;
if (now.dir == UP || now.dir == DOWN)
if (nextDir == LEFT || nextDir == RIGHT)
nextCost += 500;
if (now.dir == LEFT || now.dir == RIGHT)
if (nextDir == UP || nextDir == DOWN)
nextCost += 500;
if (nextCost < cost[nextY][nextX][nextDir]) {
cost[nextY][nextX][nextDir] = nextCost;
q.push({ nextY, nextX, nextCost, nextDir });
}
}
}
answer = *min_element(cost[n - 1][n - 1], cost[n - 1][n - 1] + 4);
return answer;
}
✔ 그냥 일반큐 사용하여 BFS 로 풀어도 상관 없다.
위 풀이는 위위 풀이에서 우선순위큐를 그냥 일반 큐로 바꾼 것 말고는 차이가 없다.
- 어차피 정점마다 4가지 방향별로 최소비용을 4 개씩이나 저장을 하기 때문에 그냥 BFS 방식으로 가장 먼저 들어간 것이 제일 먼저 방문되는 일반 큐를 사용해도 결과는 똑같았다. 방향별 최소비용이 다 저장이 되서 그런듯 하다. 우선순위큐 사용할 이유가 없었는지도 모른다.
- 큐는 자연스럽게 줄어들 수 밖에 없다. 각각 x,y,dir 그 위치의 4가지 방향에 대해 최소값만 남게되면 더 이상 큐에 푸쉬가 안되기 때문이다.
3️⃣ DFS 를 사용한 풀이
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 999999
#define DOWN 0
#define RIGHT 1
#define UP 2
#define LEFT 3
int deltaY[4] = { 1, 0, -1, 0 };
int deltaX[4] = { 0, 1, 0, -1 };
int n = 0;
int minDest = INF; // 현재까지 찾은 출발지->목적지 까지의 최~~~소의 비용
int cost_4Dir[25][25][4];
void DFS(vector<vector<int>>& board, int y, int x, int curCost, int dir) {
// 현재 방문 정점 (y, x) 에 방향은 dir, 그리고 현재까지의 비용은 curCost
/* 시간 효율성 높이는 기능! */
// return 조건 1 (더 이상 이 경로는 검사 X ) : 현재까지 찾은 최소값보다 더 커질 때! 더 이상 검사할 필요가 없음
if (minDest < curCost)
return;
// return 조건 2 (더 이상 이 경로는 검사 X ) : 목적지에 도착했을 떄
if (y == n - 1 && x == n - 1) {
minDest = min(curCost, minDest);
return;
}
// 4가지 방향 중 다음 방문 후보 검사
for (int i = 0; i < 4; ++i) {
int nextY = y + deltaY[i];
int nextX = x + deltaX[i];
if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= n || board[nextY][nextX] == 1)
continue;
int nextCost = curCost + 100;
if (dir == UP || dir == DOWN)
if (i == LEFT || i == RIGHT)
nextCost += 500;
if (dir == LEFT || dir == RIGHT)
if (i == UP || i == DOWN)
nextCost += 500;
if (cost_4Dir[nextY][nextX][i] > nextCost) {
cost_4Dir[nextY][nextX][i] = nextCost;
DFS(board, nextY, nextX, nextCost, i); // 바로 방문하러 ㄱㄱ
}
}
}
int solution(vector<vector<int>> board) {
int answer = 0;
n = board.size();
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int k = 0; k < 4; ++k)
cost_4Dir[i][j][k] = INF;
DFS(board, 0, 0, 0, -1);
answer = minDest;
return answer;
}
위의 BFS 풀이랑 똑같이 풀면 된다. 큐에 예약하는 부분을 재귀로 DFS 함수를 호출하여 또 깊게 들어가는식으로 코드를 짜면 된다. DFS 에선 예약하지 않고 그냥 다음 방문할 후보를 보면 냅다 방문하러 들어가버리기 때문! 그리고 목적지 (n-1, n-1)에 도달하면 return 하여 되돌아오게끔 하면 된다.
if (minDest < curCost)
return;
다만 DFS 는 깊이 있는데로 다 들어가기 때문에 시간초과가 날 수도 있다!! 그렇기 때문에 현재까지 구한 목적지까지의 최소비용인 minDest보다 현재까지 구한 최소비용이 더 크다면 이 경로는 minDest를 업데이트 할 수 있는 경로가 아니므로 return 한다. 이렇게만 해주면 시간 초과 나지 않았다.
마찬가지로! DFS 도 방향까지 저장하여 최소비용을 업데이트 하는데에 3 차원 배열을 사용하였다.
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기