문제
https://school.programmers.co.kr/learn/courses/30/lessons/67259
입력
도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board
출력
경주로를 건설하는데 필요한 최소 비용
풀이
제한조건
- board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
- board 배열의 각 원소의 값은 0 또는 1 입니다.
- 도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다.
- 원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
- board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
- 출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다
접근방법
BFS 탐색으로 해결했다.
IDEA1. 3차원 배열
3차원 배열을 이용해서 각 지점에서의 방향까지 고려하여
BFS를 수행하는 방식을 생각했다.
하지만 결국 중요한것은 비용이므로, 방향과 관계없이 비용만의 최소를 다루기 위해 해당 방법은 사용하지 않았다.
가능한 방식이다. 다른 방법을 사용했을 뿐
IDEA2. 2차원 배열_1
처음 구현 시에는 Car라는 클래스를 만들어서 좌표와 방향만을 고려하며 비용을 정산하며 진행했다.
class Car {
int x; // x좌표
int y; // y좌표
int dir; // 현재 방향
Car(int a, int b, int c) {
x = a;
y = b;
dir = c;
}
}하지만 문제가 있었는데, 아래와 같은 예시가 있다고 생각해보자.
00000
01110
00100
10001
01100처음에 탐색을 시작한 방향에 따라 비용이 달라지는데
- 아래로 시작한 경우
- 직선 8개, 커브 5개 = 3300
- 우측으로 시작한 경우
- 직선 10개 커브 4개 = 3000이런 케이스가 문제가되는 이유는 초기에 양쪽으로 갈라져서 탐색을 하다가 (3,3) 지점에서 처음 만나게 된다.
이때 (3,3)지점에서 처음 다시 만나면서 발생하는 비용이 다르다.
- 비용에 0.01을 곱하여 나타냄.
1 2 3 4 5
2 벽 벽 벽 11
3 9 벽 18 12
벽 15 21 ? 벽
0 벽 벽 0 0?로 표시된 지점의 위쪽에서 접근한 경우
- 비용에 0.01을 곱하여 나타냄.
1 2 3 4 5
2 벽 벽 벽 11
3 9 벽 18 12
벽 15 21 24 벽
0 벽 벽 25 31?로 표시된 지점의 왼쪽에서 접근한 경우
- 비용에 0.01을 곱하여 나타냄.
1 2 3 4 5
2 벽 벽 벽 11
3 9 벽 18 12
벽 15 21 22 벽
0 벽 벽 28 34결과적으로 ?자리에 처음 위치했을때 비용이 더 비싸지만 오히려 최종 결과는 더 저렴한 케이스가 있다.
문제는 처음 3차원 배열을 사용하는 방안을 포기하고 2차원으로 진행했기 때문에 이러한 문제에서 대처할 방법이 없었다.
그래서 Car 클래스를 수정하여 현재 비용을 전부 가지고 있게 처리하고 비용을 계산하는 방법을 변경했다.
1. 이미 방문한적이 있나?
2. 방문한 적이 있다면, 방향 전환으로 인한 비용 차이를 감당하고도 갈 가치가 있는가?방향 전환으로 인해 생길 수 있는 감당 가능한 비용은 커브로 인한 비용 500이다. 해당 케이스만 고려해 준다면, 시간초과와 메모리 초과에서 벗어날 수 있다.
코드
import java.util.*;
class Car {
int x; // x좌표
int y; // y좌표
int dir; // 현재 방향
int cost; // 현재까지의 비용
Car(int a, int b, int c, int d) {
x = a;
y = b;
dir = c;
cost = d;
}
}
class Solution {
int[][] visit;
int len;
public int solution(int[][] board) {
len = board.length;
visit = new int[len][len];
return search(board);
}
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
public int search(int[][] board) {
Queue<Car> q = new ArrayDeque();
q.add(new Car(0, 0, 1, 100)); // 아래쪽을 바라보는 차량
q.add(new Car(0, 0, 3, 100)); // 오른쪽을 바라보는 차량
visit[0][0] = 100;
int answer = Integer.MAX_VALUE;
while (!q.isEmpty()) {
Car cur = q.poll();
if (cur.x == len - 1 && cur.y == len - 1) {
answer = Math.min(answer, cur.cost);
continue;
}
// 4가지 방향으로 탐색
for (int d = 0; d < 4; ++d) {
int nextX = cur.x + dx[d];
int nextY = cur.y + dy[d];
// 범위 내부이면서, 벽이 아닌경우 도로를 건설할 수 있다.
if (isInRange(nextX, nextY) && board[nextX][nextY] == 0) {
// 방향의 변화 여부에 따라 건설비용이 달라진다.
int weight = cur.dir == d ? 100 : 600;
// 한번도 가지 않은 경우
if (visit[nextX][nextY] == 0) {
visit[nextX][nextY] = cur.cost + weight;
q.add(new Car(nextX, nextY, d, cur.cost + weight));
} else if (cur.cost + weight < visit[nextX][nextY] + 500) {
// 간 적이 있지만, 비용적으로 이득이 발생하는 부분
visit[nextX][nextY] = cur.cost + weight;
q.add(new Car(nextX, nextY, d, cur.cost + weight));
} else {
// nothing
}
}
}
}
return answer - 100;
}
public boolean isInRange(int x, int y) {
if (0 <= x && x < len && 0 <= y && y < len)
return true;
return false;
}
}