[코테] 백준 17484번 : 진우의 달 여행 (java)

❓문제

https://www.acmicpc.net/problem/17484

17484번: 진우의 달 여행 (Small)

 

 

---

🔅해석

문제 분류가 DP와 브루트포스 알고리즘으로 분류되어 dfs로 접근해야겠다고 생각했다.

 

1. 깊이우선탐색으로 지구에서 달까지 가는 경로를 다 탐색한다.

 

2. 단, 같은 방향으로 2번 이상 갈 수 없으니, 이전 방향과는 다르게 전진해야한다.

→ 갈 수 있는 방향은 미리 배열로 선언해둔다. dirY = {-1, 0, 1};

 

3. 마지막 단계에서 해당 경로의 연료를 계산한다.

min값과 비교하여 해당 경로의 연료가 더 적으면 min에 해당 경로의 연료를 대입한다.

 

---

⭕정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N,M;
	static int[][] arr;
	static int min = Integer.MAX_VALUE;
	static int[] dirY = {-1, 0, 1};		//갈 수 있는 방향
	static int[] visited;
	
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new int[N][M];
		
		//지구 - 달 행렬 생성
		for (int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=0; j<M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//M번을 시작으로 dfs로 모든 경로를 방문한다.
		for (int i=0; i<M; i++) {
			visited = new int[N];
			visited[0] = i;
			dfs(1, i, -1);
		}
		
		System.out.println(min);
		br.close();
	}

	private static void dfs(int depth, int x, int dir) {	//y위치, x위치, 방향
		
		//달로 도착하는 마지막 단계
		if (depth == N) {
			int sum = 0;
			for (int i=0; i<N; i++) {
				sum += arr[i][visited[i]];// 해당 경로의 연료를 계산한다.
			}
			
			min = min > sum ? sum : min;
			return;
		}
		
		//이전 방향과 다르게 전진한다.
		for (int i=0; i<3; i++) {	//3종류의 방향
			int nx = x + dirY[i];	//방향의 따른 x위치 결정
			if (isVaildPosition(nx) && dir != i) {	//x위치가 배열 안에 있고, 방향이 이전 방향과 다를 때
				visited[depth] = nx;				//x위치 값 저장
				dfs (depth+1, nx, i);				//다음 y로 이동
			}
		}
	}
	
	//현재 x가 배열의 범위 안에 있는지 검사
	private static boolean isVaildPosition(int x) {
		if (x>=0 && x < M) {
			return true;
		}
		return false;
	}
}

 

---

❗결과