[백준] 17484번 진우의 달 여행 JAVA (자바) 풀이

문제 17484 

• 지구와 우주사이는 N X M 행렬
• 각 원소의 값 = 지날 때 소모되는 연료 양
• 연지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 연료의 최소값을 구해라

 

• 지구 → 달 경우 우주선 이동 가능 방향

 

• 우주선 이전에 움직인 방향으로 움직일 수 없다 (같은 방향으로 두번 연속 이동 불가)

 

[입력]

 

 :  첫 번째 줄 지구와 달 사이 공간을 나타내는 행렬 크기 N, M ( 2≤  N, M ≤ 6 )

 
 :  N줄 동안 각 행렬의 원소 값 ( 행렬의 원소값은 100 이하의 자연수 )

 

6 4
5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

 

 

 [출력]

 :  최소 연료의 값

 

29

 

 

     

 

 [코드]

import java.io.*;
import java.util.*;

class Main{    
    static int n,m;
    static int arr[][];
    static int min = Integer.MAX_VALUE;
    static int[] dy = {-1, 0, 1};
    static int[] visit;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        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());
            }
        }

        for(int i=0; i<m; i++) {
            visit = new int[n];
            visit[0] = i;
            brute(1, i, -1);
        }

        System.out.println("" + min);
        
    }

    public static void brute(int layer, int y, int dir) {
        if(layer == n) {
            int sum = arr[0][visit[0]];
            for(int i=1; i<n; i++) {
                sum += arr[i][visit[i]];
            }

             min = Math.min(min, sum);
            return;
        }

        for(int i=0; i<3; i++) {
            int nowy = y + dy[i];
            if(position(nowy) && dir != i) {
                visit[layer] = nowy;
                brute(layer+1, nowy, i);
            }
        }
    }

    public static boolean position(int y) {
        if(y < 0 || y >= m)
            return false;
        return true;
    }
}

 

 [해설]
     

 :  static int n,m;
    static int arr[][];
    static int min = Integer.MAX_VALUE;  최소 합 저장 
    static int[] dy = {-1, 0, 1};  아래 / 아래 대각선 → 즉 y 좌표만 이동한다
    static int[] visit;  방문기록

 :  st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());  첫번째줄 입력 행
    m = Integer.parseInt(st.nextToken());  첫번째줄 입력 열
    arr = new int[n][m];  2차원 배열 생성

 :  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());  배열판에 입력받기
        }
    }

 :  for(int i=0; i<m; i++) {
       visit = new int[n]; 방문배열 초기화
       visit[0] = i;  열 단위로 검사
       brute(1, i, -1);  완전탐색 시작
    }

 :  System.out.println("" + min);  최소합 출력
           
 
 :  public static void brute(int layer, int y, int dir) {  
        if(layer == n) {  마지막 행 탐색할 때 종료
            int sum = arr[0][visit[0]]; 
            for(int i=1; i<n; i++) {
                sum += arr[i][visit[i]]; 합계산
            }
             min = Math.min(min, sum);  최소합 계산
            return;
        }

        for(int i=0; i<3; i++) {
            int nowy = y + dy[i]; 현 y 좌표
            if(position(nowy) && dir != i) { 새로운 nowy가 유효한 범위 내에 있고 이전에 이동한 방향 아닐 경우

                visit[layer] = nowy;  현재 행에서 선택한 열의 인덱스를 기록
                brute(layer+1, nowy, i); 다시 brute 시작
            }
        }
    }

    public static boolean position(int y) { y값 범위 계산
        if(y > 0 || y >= m)
            return false;
        return true;
    }
}



 

 

이제 풀어보러 갈께요 :)

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

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

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