[알고리즘] 경주로 건설 (2020 카카오 인턴십)

코딩테스트 연습 - 경주로 건설

 일단 최소비용 + 최단거리 경로 탐색 문제이다. 여러가지 방법들로 풀던데 난 처음엔 dfs를 이용해서 브루트포스 방식으로 했다. 하지만 이 방식의 문제점은 depth가 깊어질수록 4방향으로 모두 탐색을 하기에 4 ^ 노드수 만큼의 탐색을 하게 된다. 결국 시간초과가 발생하는 테스트 케이스가 생겼다.

 

 그 다음엔 dfs + dp의 방법을 생각했으나 이 방법으론 풀 수 없는 것이, '코너' 라는 속성의 판단은 기본적으로 이전 노드 위치를 필요로 하기 때문에 (현재 x, 현재 y) 로부터 (N-1, N-1) 까지의 최소비용을 구하는 dfs + dp 방법으로는 풀 수가 없겠다는 생각이 들었다.

 

 그렇기 때문에 생각을 바꾸어서 어차피 최소비용은 최단거리 경로 중 하나에서 나올 것이기에 (0, 0) 으로부터 (현재 x, 현재 y)까지의 최소 비용을 저장하는 배열을 만들어 놓고 bfs 탐색으로 최단 경로를 탐색 하되 이미 방문한 노드라도 현재까지의 비용이 이전에 저장된 비용보다 더 적은 경우는 다시 방문이 가능하도록 했다.

 이렇게 되면 최단경로를 찾아서 시간복잡도 문제를 해결함과 동시에 최소비용이 발생하는 경우에만 재탐색을 하기에 최소비용 또한 찾을 수 있다.

 

import java.util.*;


class Solution {

	static boolean[][] visited;
	static int[][] min_cost;

	static int min = Integer.MAX_VALUE;

	public static int solution(int[][] board) {

		int N = board.length;

		Queue<Node> queue = new LinkedList<>();

		visited = new boolean[N][N];
		min_cost = new int[N][N];
		visited[0][1] = true;
		visited[1][0] = true;

		if(board[0][1] == 0)
			queue.offer(new Node(0, 0, 0, 1, 100));
		if(board[1][0] == 0)
			queue.offer(new Node(0, 0, 1, 0, 100));

		while(!queue.isEmpty())
		{
			Node node = queue.poll();

			int former_x = node.former_x;
			int former_y = node.former_y;
			int current_x = node.current_x;
			int current_y = node.current_y;
			int cost = node.cost;

			if(current_x == N-1 && current_y == N-1)
			{
				min = Math.min(cost, min);
			}
			else {
				int x[] = {-1, 1, 0, 0};
				int y[] = {0, 0, -1, 1};

				for (int i = 0; i < 4; i++)
				{
					int next_x = current_x + x[i];
					int next_y = current_y + y[i];

					if (0 <= next_x && next_x < N && 0 <= next_y && next_y < N)
					{
						if(board[next_x][next_y] == 0)
						{
							int next_cost = cost + 100;

							if (isCorner(next_x, next_y, former_x, former_y))
								next_cost += 500;

							if (!visited[next_x][next_y])
							{
								visited[next_x][next_y] = true;
								min_cost[next_x][next_y] = next_cost;
								queue.offer(new Node(current_x, current_y, next_x, next_y, next_cost));
							}
							else
							{
								if(min_cost[next_x][next_y] >= next_cost)
								{
									min_cost[next_x][next_y] = next_cost;
									queue.offer(new Node(current_x, current_y, next_x, next_y, next_cost));
								}
							}
						}
					}
				}
			}

		}

		return min_cost[N-1][N-1];
	}

	static class Node{

		int current_x, current_y, former_x, former_y, cost;

		public Node() {
		}

		public Node(int former_x, int former_y, int current_x, int current_y, int cost) {
			this.current_x = current_x;
			this.current_y = current_y;
			this.former_x = former_x;
			this.former_y = former_y;
			this.cost = cost;
		}
	}

	static boolean isCorner(int next_x, int next_y,int former_x, int former_y)
	{
		if(Math.abs(next_x - former_x) == 1 && Math.abs(next_y - former_y) == 1)
			return true;
		return false;
	}


}