[프로그래머스 - Java] 경주로 건설 (2020 카카오 인턴십)

문제

programmers.co.kr/learn/courses/30/lessons/67259

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

설명

DFS로 모든 경로를 찾고, 경로마다 비용을 계산하며 최소 비용을 구하면 되겠다 생각도 했지만 이렇게 하면 시간 초과에 너무 비효율적.

 

BFS로 도착점까지의 최단 경로를 찾되,

이전 경로에서 구한 비용보다 더 작은 비용을 구하게 된다면 더 작은 비용으로 갱신하며 풀어나가면 된다!

1. 경주로 정보를 저장하는 클래스

class Point {
	int x; 
	int y;
	int dir;
	int cost;

	Point(int x, int y, int dir, int cost) {
		this.x = x;
		this.y = y;
		this.dir = dir;
		this.cost = cost;
	}
}

 

이차원 배열이기에 클래스를 만들어 x, y 좌표를 관리했다.

추가로 방향과 비용을 저장할 dir, cost 변수도 추가했다.

dir은 현재 움직이는 방향(바라보고 있는 방향)의 값을 가짐 (0 ~ 3까지 - *dx, dy 배열에 따라)

cost는 해당 좌표의 위치까지 도달하는데 걸린 비용의 값을 가짐 

 

*dx, dy 배열이란?

2차원 배열에서 상 하 좌 우 이동해야 하는 경우가 알고리즘 문제에서 종종 나온다.

이때 x, y 이동을 편리하게 하기 위해 dx, dy 배열을 만들어 두면 좋다.

 

 

인덱스 0, 1, 2, 3의 순으로 상, 좌, 하, 우라고 외우면 좋다.

위의 그림에서 상은 (-1, 0) 부터 시작하고 반시계 방향으로 우까지 돌아가는 순이다.

이를 배열로 나타내면 아래와 같다. 

 

 

 

예를 들어 현재 2차원 배열의 (2, 2)에 상어가 있다.

여기서 위쪽으로 가려면 (2, 2) + (-1, 0) => (1, 2)

왼쪽은 (2, 2) + (0, -1) => (2, 1)

아래쪽은 (2, 2) + (1, 0) => (3, 2)

오른쪽은 (2, 2) + (0, 1) => (2, 3) 

이런식으로 dx, dy의 방향에 따른 인덱스 값을 현재 좌표 값에 더해서 위치를 간단히 이동시킬 수 있다!

 

 

2. BFS 구현 

큐를 생성하고 시작점인 (0, 0)부터 시작한다.

방향은 처음 시작이라는 의미로, 0, 1, 2, 3의 값이 아닌 -1을 주었고,

비용은 0

visited 배열의 경우 방문했다는 의미로 1을 주었다.

 

*기존 BFS에서 visited배열은 boolean 값을 담는 배열로 방문했는지 안 했는지에 따라 T/F값만 체크했었다.

하지만 지금은 BFS로 최단 경로 탐색을 하면서, 이미 방문한 곳이라도 비용이 더 적게 든다면 재방문이 가능해야 한다!

따라서 int형 배열로 비용의 정보를 저장하도록 만들었다. (초기값 0인 경우가 방문하지 않은 경우가 된다.)

(이름은 cost 이런 걸로 할까 하다가 그냥 visited 한 것이니 신경 쓸 필요 X)

 

 public static void bfs(int[][] board) {
	Queue<Point> queue = new LinkedList<>();
	queue.add(new Point(0, 0, -1, 0)); 
	visited[0][0] = 1;
    
	while(!queue.isEmpty()) {
		// 밑의 설명에서 추가할 것 
	}
}

 

 

기존의 BFS 코드와 비슷하지만, 비용을 구하는 부분이 추가되었고

이미 방문한 곳이더라도, 어떤 경로로 왔든 이전 경로의 비용보다 새로운 비용이 같거나 작다면 갱신되어야 한다.

 

새로운 비용 계산 방법

먼저 처음 시작점에서 왔거나 이전의 방향과 같은 경우는 무조건 직선 도로이기에 현재 cost 값에 100원 추가

방향이 다른 경우라면 무조건 코너 -> 코너라도 직선 도로를 타고 오기에 현재 cost 값에 600원 추가

방문하지 않은 경우

새로이 구해진 비용을 visited배열에 넣고, 큐에도 새로운 비용을 가진 Point를 추가한다.

이미 방문한 경우 

이미 방문한 경우라도, 새로이 구해진 비용이 이전에 구해진 visited에 저장된 비용보다 작거나 같다면 값을 경신해줘야 한다.

작은 경우만 따지는 것이 아니라 같은 경우 역시 확인해야 하는 이유는

같은 경우의 좌표로부터 새롭게 경로를 찾아가면서 그보다 최소 비용을 가지는 경로를 찾을 수도 있기 때문이다.

도착점에 도달한 경우

BFS를 수행하면서 이미 방문한 곳이라도 비용이 작다면 재방문한다.

그렇기에 도착점에 다른 비용으로 여러 번 올 수 있다.

 

도착점까지의 비용 중 가장 적은 값을 min 변수에 저장하고, 모든 BFS가 끝난 후 min을 출력하면 된다.

 

while(!queue.isEmpty()) {
	int cx = queue.peek().x;
	int cy = queue.peek().y;
	int cd = queue.peek().dir;
	int cost = queue.poll().cost;

	// 도착점에 도달한 경우 
	if(cx ==  N-1 && cy == N-1) { 
		min = Math.min(min, cost);
		continue; 
	}

	// 상 하 좌 우 새로운 포인트 검사 
	for(int i = 0; i < 4; i++) { 
		int nx = cx + dx[i];
		int ny = cy + dy[i];
		int nd = i;

		// 범위 넘어가거나, 벽인 경우 pass 
		if(nx < 0 || ny < 0|| nx >= N || ny >= N || board[nx][ny] == 1) 
			continue;	

		// 새로운 비용 구하기
		int newCost = cost; 
		if(cd == -1 || cd == nd) // 처음 시작이거나 방향 같은 경우 -> 직선
			newCost += 100; 
		else 
			newCost += 600; // 직선 + 코너 


		if(visited[nx][ny] == 0) { // 방문하지 않은 경우 
			visited[nx][ny] = newCost;
			queue.add(new Point(nx, ny, nd, newCost));
		} else if(visited[nx][ny] >= newCost) { 
			// 이미 방문한 경우, 비용이 더 작은 값으로 갱신 
			visited[nx][ny] = newCost; 
			queue.add(new Point(nx, ny, nd, newCost));
		}
	}
}

전체 코드 (주석 간결 버전)

import java.util.LinkedList;
import java.util.Queue;

class Point {
	int x; 
	int y;
	int dir;
	int cost;

	Point(int x, int y, int dir, int cost) {
		this.x = x;
		this.y = y;
		this.dir = dir;
		this.cost = cost;
	}
}

class Solution {
    public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, -1, 0, 1};
	public static int N;
	public static int[][] visited;
	public static int min = Integer.MAX_VALUE;
    
    public int solution(int[][] board) {
		N = board.length;
		visited = new int[N][N];
		
		bfs(board);

		return min;
    }
    
   public static void bfs(int[][] board) {
		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(0, 0, -1, 0)); 
		visited[0][0] = 1;

		while(!queue.isEmpty()) {
			int cx = queue.peek().x;
			int cy = queue.peek().y;
			int cd = queue.peek().dir;
			int cost = queue.poll().cost;

			// 도착점에 도달한 경우 
			if(cx ==  N-1 && cy == N-1) { 
				min = Math.min(min, cost);
				continue; 
			}

			// 상 하 좌 우 새로운 포인트 검사 
			for(int i = 0; i < 4; i++) { 
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				int nd = i;

				// 범위 넘어가거나, 벽인 경우 pass 
				if(nx < 0 || ny < 0|| nx >= N || ny >= N || board[nx][ny] == 1) 
					continue;	

				// 새로운 비용 구하기
				int newCost = cost; 
				if(cd == -1 || cd == nd) // 처음 시작이거나 방향 같은 경우 -> 직선
					newCost += 100; 
				else 
					newCost += 600; // 직선 + 코너 
				

				if(visited[nx][ny] == 0) { // 방문하지 않은 경우 
					visited[nx][ny] = newCost;
					queue.add(new Point(nx, ny, nd, newCost));
				} else if(visited[nx][ny] >= newCost) { 
					// 이미 방문한 경우, 비용이 더 작은 값으로 갱신 
					visited[nx][ny] = newCost; 
					queue.add(new Point(nx, ny, nd, newCost));
				}
			}
		}
	}
    
}

전체 코드( 주석 많은 자세한 버전)

import java.util.LinkedList;
import java.util.Queue;

class Point {
	int x; 
	int y;
	int dir; // 거리 
	int cost; // 비용 

	Point(int x, int y, int dir, int cost) {
		this.x = x;
		this.y = y;
		this.dir = dir;
		this.cost = cost;
	}
}

public class RaceWay {
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, -1, 0, 1};
	public static int N;
	public static int[][] visited;
	public static int min = Integer.MAX_VALUE;

	public static void main(String[] args) {
		int[][] b1 = {{0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,0},
				{0,0,0,0,1,0,0,0},{0,0,0,1,0,0,0,1},{0,0,1,0,0,0,1,0},
				{0,1,0,0,0,1,0,0},{1,0,0,0,0,0,0,0}};

		int[][] b2 = {{0,0,0},{0,0,0},{0,0,0}};

		System.out.println(solution(b1));
	}

	public  static int solution(int[][] board) {
		N = board.length;
		
		// 기존의 BFS에서의 visited 배열은 방문했나 안했나 T/F만 체크 
		// 하지만 지금은 BFS로 최단 경로 탐색을 하면서, 이미 방문한 곳도 비용이 더 적게 든다면 재방문이 가능해야함 
		// 따라서 int형 배열로 비용의 정보를 저장하도록 함 
		visited = new int[N][N]; 

		bfs(board);

		return min;
	}


	public static void bfs(int[][] board) {
		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(0, 0, -1, 0)); // 시작점의 dir은 -1 
		visited[0][0] = 1; // 시작점은 방문했다는 의미로 1 

		while(!queue.isEmpty()) {
			int cx = queue.peek().x;
			int cy = queue.peek().y;
			int cd = queue.peek().dir;
			int cost = queue.poll().cost;
			
			// 도착점이라면 더 작은 비용으로 갱신
			// (BFS를 통해(이미 방문한 곳이라도 cost가 작아진다면 또 방문함) 도착점에 다른 비용으로 여러번 올 수 있기 때문) 
			if(cx ==  N-1 && cy == N-1) { 
				min = Math.min(min, cost);
				continue; // 갱신했으니 다음 큐에 있는 포인트 처리 
			}

			for(int i = 0; i < 4; i++) { // 상하좌우 새로운 포인트로 이동 
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				int nd = i;

				if(nx < 0 || ny < 0|| nx >= N || ny >= N || board[nx][ny] == 1) // board 범위를 벗어나거나, 벽인 경우 pass 
					continue;	

				int newCost = cost; // 새로운 포인트의 비용은, 이전 비용의 값으로 초기화  
				if(cd == -1 || cd == nd) { // 처음 시작(-1)이거나 방향이 같은 경우 -> +무조건 직선 도로 100 
					newCost += 100; 
				} else {
					newCost += 600; // +(직선 도로 100 + 코너 500)
				}

				if(visited[nx][ny] == 0) { // 처음 방문하는 곳일 경우 
					visited[nx][ny] = newCost; // 새로운 비용으로 초기화 
					queue.add(new Point(nx, ny, nd, newCost));
				} else if(visited[nx][ny] >= newCost) { // 이미 방문한 곳이더라도, 어떤 경로로 왔든 이전 경로의 비용보다 새로운 비용이 같거나 작다면 갱신  
					visited[nx][ny] = newCost; // 무조건 작은 경우만 되는게 아니라, 같은 경우도 확인해야지 혹시나 있을지 모르는 최소 비용을 구할 수 있음
					queue.add(new Point(nx, ny, nd, newCost));
				}
			}
		}
	}


}

GITHUB

github.com/KwonMinha/Programmers/blob/master/2020_Kakao_Internship/src/RaceWay.java

GitHub - KwonMinha/Programmers: 프로그래머스 (Java) 문제 풀이