2020 카카오 인턴십 - 경주로 건설
풀이
BFS와 DFS중 DFS를 선택해서 문제에 도전했다.
DFS를 통해 모든 경로를 다 조사해서 [N-1][N-1]에 도착할 때마다 답을 업데이트하고, 최종 답을 return하는 방법으로 풀었는데 효율성에서 좋은 점수를 받지 못했다. 여러번 도전했는데 2차 도전과 동일한 테스트에서 자꾸 틀렸다고 나와 기술 블로그와 검색을 통해 어떤 아이디어로 문제를 풀었는지 확인했다.
priority_queue
문제를 다시 풀어보면서 다시 개념과 사용법에 대해서 공부했다.
반성
※ BFS를 문제를 풀 때 사용했던 고정적인 방법만 떠올리지 말자
※ 방문 여부를 표시하기 어려운 문제가 다음에 나온다면 이 문제를 생각해보자
※ 맞은 문제라도 다른 풀이를 검색해서 공부하자
※ 효율적인 주석 사용을 연습하자
카카오 기술 블로그에서 알려주는 방법!
문제 해설
최단 경로를 구하기 위해 BFS를 이용하여 살펴 보겠습니다. 먼저 출발지 → 도착지로 이동하는 [코너가 1개인 경로, 코너가 2개인 경로, 코너가 3개인 경로, …, 코너가 K개인 경로] 중 가장 적은 비용이 드는 경로를 찾습니다. 예를 들어 예제 1번 [[0,0,0],[0,0,0],[0,0,0]]의 경우 코너가 1개이면서 가장 적은 비용이 드는 경로는 다음과 같이 2 가지입니다.
- (0,0) → (0,1) → (0,2) → (1,2) → (2,2)
- (0,0) → (1,0) → (2,0) → (2,1) → (2,2)
코너가 2개이면서 가장 적은 비용이 드는 경로 중 하나는 다음과 같습니다.
- (0,0) → (0,1) → (1,1) → (2,1) → (2,2)
이 외에도 다양한 경로가 있으며, 코너가 K개일 때 가장 적은 비용이 들려면 직선 도로 개수를 최대한 줄이면 됩니다. 이는 코너를 K개 만들면서 출발지에서 도착지까지 가는 최단 경로를 찾으면 됩니다.
이제 다음과 같이 상태 공간 S를 정의합니다.
- S = [세로 좌표 R][가로 좌표 C][코너 개수 K][바라보는 방향 D] → 코너 K개를 만들면서 (R, C) 위치에 도착했고, D방향을 바라보고 있을 때의 최단 거리
이때 한 칸 이동하는데 드는 비용은 1, 코너를 하나 만드는 비용도 1이라고 가정합니다. 이제 출발지 → 도착지로 이동하는 최단 경로를 모든 K에 대해서 찾아줍니다. BFS 탐색 코드는 다음과 같이 작성합니다.
- 마지막으로 바라본 방향을 기준으로 왼쪽 회전, 오른쪽 회전, 직진 하는 3가지 경우에 대해 탐색합니다.
- 왼쪽 회전, 오른쪽 회전의 경우 코너를 하나 추가하고, 바라보는 방향을 바꿔줍니다.
- 직진의 경우 바라보는 방향으로 1칸 전진합니다.
위와 같이 BFS 탐색을 한 후, 마지막으로 (N – 1, N – 1) 위치에서 K = 1, 2, 3, … 인 경우에 대해 최단 거리를 찾아주면 됩니다. 이때, 주의 할 점은 여기서 구한 최단 거리는 코너 개수가 포함된 값이라는 것입니다. 따라서 코너가 K개인 최단 거리에서 건설 비용은 다음과 같이 계산하면 됩니다.
- (최단 거리 – K) x 100 + K * 500
그렇다면 여기서 K값은 얼마나 커질 수 있을까요? 각 격자칸 하나에는 코너가 최대 1개 생길 수 있습니다. 그렇다면 N x N 크기 격자에서 코너 개수는 격자칸 개수보다는 작아야 합니다. 따라서 코너 개수 K는 최대 N x N이면 됩니다.
코드
1차 코드
효율성 테스트 6~12, 15~19번을 틀렸다.
#include <string>
#include <vector>
using namespace std;
int answer = 25 * 25 * 500;
int curve = 0;
int dy[] = {-1,1,0,0};
int dx[] = {0,0,1,-1};
bool range_check(int y, int x, int length, vector<vector<int>> &board){
if(y < 0 || x < 0 || y >= length || x >= length) return false;
if(board[y][x] < 0 || board[y][x] == 1) return false;
return true;
}
// 지금 y,x 위치, 지금 방향, 격자 사이즈, 이차원배열
void go_next_step(int y, int x, int dir, int length, vector<vector<int>> &board){
if(y == length -1 && x == length - 1){
int cost = (abs(board[y][x]) - 1) * 100 + 500 * curve;
if(answer > cost) answer = cost;
return;
}
// 다음 격자칸에 들어왔으니까
for(int i = 0 ; i < 4 ; i++){
int nexty = y + dy[i];
int nextx = x + dx[i];
if(range_check(nexty, nextx, length, board)){
if(i != dir) curve++;
board[nexty][nextx] = board[y][x] - 1;
go_next_step(nexty, nextx, i, length, board);
board[nexty][nextx] = 0;
if(i != dir) curve--;
}
}
}
int solution(vector<vector<int>> board) {
int board_size = (int)board.size();
board[0][0] = -1;
for(int i = 0 ; i < 4 ; i++){
int nexty = dy[i];
int nextx = dx[i];
if(range_check(nexty, nextx, board_size, board)){
board[nexty][nextx] = board[0][0] - 1;
go_next_step(nexty, nextx, i, board_size, board);
board[nexty][nextx] = 0;
}
}
return answer;
}2차 코드
효율성 테스트 10~11, 17~19번을 틀렸다.
#include <string>
#include <vector>
using namespace std;
int answer = 25 * 25 * 400;
int curve = 0;
int dy[] = {-1,1,0,0};
int dx[] = {0,0,1,-1};
bool range_check(int y, int x, int length, vector<vector<int>> &board){
if(y < 0 || x < 0 || y >= length || x >= length) return false;
if(board[y][x] < 0 || board[y][x] == 1) return false;
return true;
}
// 지금 y,x 위치, 지금 방향, 격자 사이즈, 이차원배열
void go_next_step(int y, int x, int dir, int length, vector<vector<int>> &board){
=> 여기에 조건 추가!!!
if((abs(board[y][x]) - 1) * 100 + 500 * curve > answer) return;
if(y == length -1 && x == length - 1){
int cost = (abs(board[y][x]) - 1) * 100 + 500 * curve;
if(answer > cost) answer = cost;
return;
}
// 다음 격자칸에 들어왔으니까
for(int i = 0 ; i < 4 ; i++){
int nexty = y + dy[i];
int nextx = x + dx[i];
if(range_check(nexty, nextx, length, board)){
if(i != dir) curve++;
board[nexty][nextx] = board[y][x] - 1;
go_next_step(nexty, nextx, i, length, board);
board[nexty][nextx] = 0;
if(i != dir) curve--;
}
}
}
int solution(vector<vector<int>> board) {
int board_size = (int)board.size();
board[0][0] = -1;
for(int i = 0 ; i < 4 ; i++){
int nexty = dy[i];
int nextx = dx[i];
if(range_check(nexty, nextx, board_size, board)){
board[nexty][nextx] = board[0][0] - 1;
go_next_step(nexty, nextx, i, board_size, board);
board[nexty][nextx] = 0;
}
}
return answer;
}
최종 코드 - 1
#include <string>
#include <vector>
#include <queue>
using namespace std;
const int INF = 25 * 25 * 500;
int dist[26][26][4]; // y,x,dir;
int dy[] = {0,-1,0,1};
int dx[] = {-1,0,1,0};
typedef struct{
int y, x, cost, direction;
}state;
struct cmp {
bool operator () (state& s1, state& s2){
return s1.cost > s2.cost;
}
};
int solution(vector<vector<int>> board) {
int len = (int)board.size();
int answer = INF;
for(int i = 0 ; i < 26 ; i++)
for(int j = 0 ; j < 26 ; j++)
for(int k = 0 ; k < 4 ; k++) dist[i][j][k] = INF;
priority_queue<state, vector<state>, cmp> pq;
// 시작지점에 dist 0으로 변경 -> pq에 넣어주기
dist[0][0][0] = 0;
dist[0][0][1] = 0;
dist[0][0][2] = 0;
dist[0][0][3] = 0;
pq.push({0,0,0,0});
pq.push({0,0,0,1});
pq.push({0,0,0,2});
pq.push({0,0,0,3});
while(!pq.empty()){
state S = pq.top();
pq.pop();
int y = S.y;
int x = S.x;
int cost = S.cost;
int dir = S.direction;
// 4방향 이동
for(int i = 0 ; i < 4 ; i++){
int nexty = y + dy[i];
int nextx = x + dx[i];
// 다시 이전 칸으로 돌아간다면 continue 해주기
if(abs(dir - i) == 2) continue;
// 범위 벗어남
if(nexty < 0 || nextx < 0 || nexty >= len || nextx >= len) continue;
// 벽이 있음
if(board[nexty][nextx] == 1) continue;
int money = 100;
if(dir != i) money += 500;
int nextCost = cost + money;
// 이 부분이 중요! 지금 새로 들어온 nextCost가 기존에 있던 dist보다 작다면 업데이트해준다
if(dist[nexty][nextx][i] > nextCost){
dist[nexty][nextx][i] = nextCost;
pq.push({nexty, nextx, nextCost, i});
}
}
}
for(int i = 0 ; i < 4 ; i++) answer = min(answer, dist[len-1][len-1][i]);
return answer;
}최종코드 - 2
#include <string>
#include <vector>
#include <queue>
using namespace std;
typedef struct{
int y, x, cost, dir;
}pos;
int dy[] = {0, -1, 0, 1};
int dx[] = {-1, 0, 1, 0};
int solution(vector<vector<int>> board) {
int len = (int)board.size();
int answer = 25 * 25 * 500;
queue<pos> q;
q.push({0,0,0,-1});
board[0][0] = 1; // 1로 설정하여 접근하지 못하도록 해준다.
while(!q.empty()){
pos P = q.front();
q.pop();
if(P.y == len-1 && P.x == len-1){
answer = min(answer, P.cost);
continue;
}
for(int i = 0 ; i < 4 ; i++){
int ny = P.y + dy[i];
int nx = P.x + dx[i];
if(abs(P.dir-i) == 2) continue; // 다시 뒤로 돌아가는 경우는 제외해준다.
if(ny < 0 || nx < 0 || ny >= len || nx >= len) continue;
if(board[ny][nx] == 1) continue;
int new_cost = 0;
// new_cost => [ny][nx]까지 오는데 걸리는 비용
if(P.dir == -1 || P.dir == i) new_cost = P.cost + 100;
else if(P.dir != i) new_cost = P.cost + 600;
if(board[ny][nx] == 0){
board[ny][nx] = new_cost;
q.push({ny, nx, new_cost, i});
}
// 처음 간 곳이 아닐 경우 비용이 더 작거나 같은 경우에 큐에 넣어준다.
if(board[ny][nx] >= new_cost){
board[ny][nx] = new_cost;
q.push({ny, nx, new_cost, i});
}
}
}
return answer;
}
옹골찬 개발자가 되기 위한 험난한 일대기