[백준] 알고리즘 분류(그래프 이론,JAVA)4485번, 녹색 옷 입은 애가 젤다지?

문제 링크

4485번: 녹색 옷 입은 애가 젤다지?

 

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 링크는 상하좌우로 이동할 수 있습니다.

2. (0, 0)에서 (N-1, N-1)에 도착할 때 최소의 도둑 루피의 최소값을 결과로 출력합니다.

3. 배열에 저장된 수들은 도둑 루피의 값을 표현합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 다익스트라를 사용해서 (N-1, N-1)의 최소 도둑 루피를 얻는 경우를 탐색합니다.

 

3. 탐색이 끝났을 때 최소 도둑 루피의 값을 결과로 출력합니다.

 

다익스트라 탐색!

 

링크가 도둑 루피를 최소로 먹어야한다. = 최단 경로 찾기

 

최단 경로 찾기 = 다익스트라 알고리즘

 

아하!!!! 다익스트라 알고리즘을 사용하라는 이야기구나!!!

 

 

다익스트라 알고리즘을 통해서 링크가 (0, 0)에서 (N-1, N-1)까지 최소 도둑 루피로 도착하는 값을 구합니다.

 

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

 

도둑 루피를 기준으로 다익스트라를 진행해서 가장 먼저 (N-1, N-1) 도착했을 때 도둑 루피 값 : 최소 도둑 루피

 

예제입력 1.

1. 입력된 정보를 저장합니다.

※1번째 테스트케이스의 경우만 보여드리겠습니다.

 

N : 3

 

5	5	4
3	9	1
3	2	7

 

2. 다익스트라를 사용해서 (N-1, N-1)의 최소 도둑 루피를 얻는 경우를 탐색합니다.

 

다익스트라 탐색 진행!

5	5	4
3	9	1
3	2	7

 

다음 지역 탐색 구역 : 도둑 루피 가장 작은 값 : (1, 0)

 

 

5	5	4
3(8)	9	1
3	2	7

 

다음 지역 탐색 구역 : 도둑 루피 가장 작은 값 : (0, 1)

 

 

5	5(10)	4
3(8)	9	1
3	2	7

 

다음 지역 탐색 구역 : 도둑 루피 가장 작은 값 : (2, 0)

 

 

5	5(10)	4
3(8)	9	1
3(11)	2	7

 

다음 지역 탐색 구역 : 도둑 루피 가장 작은 값 : (2, 1)

 

 

5	5(10)	4
3(8)	9	1
3(11)	2(13)	7

 

다음 지역 탐색 구역 : 도둑 루피 가장 작은 값 : (0, 2)

 

 

5	5(10)	4(14)
3(8)	9	1
3(11)	2(13)	7

 

다음 지역 탐색 구역 : 도둑 루피 가장 작은 값 : (0, 2)

 

 

5	5(10)	4(14)
3(8)	9	1(15)
3(11)	2(13)	7

 

다음 지역 탐색 구역 : 도둑 루피 가장 작은 값 : (1, 1)

 

 

5	5(10)	4(14)
3(8)	9(17)	1(15)
3(11)	2(13)	7

 

다음 지역 탐색 구역 : 도둑 루피 가장 작은 값 : (1, 1)

 

 

5	5(10)	4(14)
3(8)	9(17)	1(15)
3(11)	2(13)	7(20)

 

(N-1, N-1) 가장 먼저 도착!!!

 

얻은 도둑 루피 : 20개

 

탐색종료!!

 

3. 탐색이 끝났을 때 최소 도둑 루피의 값을 결과로 출력합니다.

 

얻은 도둑 루피의 수 : 20개 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 동굴의 대한 정보를 띄어쓰기 기준 나누었습니다.
• bfs함수를 실행하여 링크가 (N-1, N-1)에 도달할 때 얻는 최소 도둑 루피를 구합니다.
• 각 테스트케이스마다 얻은 최소 도둑 루피를 StringBuilder에 저장합니다.
• 모든 테스트케이스가 종료되었을 때 System.out.print()으로 StringBuilder에 저장된 결과를 출력합니다.

• bfs함수는 다익스트라 탐색을 통해서 (N-1, N-1)까지 도달하는 최소 도둑 루피를 탐색합니다.
• inSpace함수는 좌표가 동굴에 존재하는지 확인합니다.

 

결과코드

 

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

public class Main {
    //링크가 이동 관련 정보 클래스
    static class Pos implements Comparable<Pos>{
        int r, c, m;	//r : row, c : column, m : 도둑 루피 수
        public Pos(int r, int c, int m) {
            this.r = r;
            this.c = c;
            this.m = m;
        }
        @Override
        //도둑 루피 수 기준 오름차순
        public int compareTo(Pos o) {
            return this.m - o.m;
        }
    }
    static int[][] map;		// 동굴 정보 저장 배열
    static int[] dr = {-1, 1, 0, 0};	//r값 상하좌우 이동값
    static int[] dc = {0, 0, -1, 1};	//c값 상하좌우 이동값
    static int N;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedWriter
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값들 저장할 StringBuilder
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int idx = 1;
        //테스트케이스마다 최소 도둑 루피 구하기 진행!
        while(true) {
            N = Integer.parseInt(br.readLine());
            if(N==0)	//테스트케이스 종료!
                break;
            map = new int[N][N];
            //현재 테스트케이스 동굴의 정보 저장
            for(int i=0;i<N;i++) {
                st = new StringTokenizer(br.readLine()," ");
                for(int j=0;j<N;j++)
                    map[i][j] = Integer.parseInt(st.nextToken());
            }
            //다익스트라를 통한 최소 도둑 루피 값 StringBuilder에 저장
            sb.append("Problem ").append(idx).append(": ").append(bfs()).append("\n");
            idx++;
        }
        System.out.print(sb);	//StringBuilder에 저장된 결과들 출력!
        br.close();
    }
    //다익스트라 + BFS를 통해 (0, 0) -> (N-1, N-1)으로 가는 최단 도둑 루피 경로를 탐색합니다.
    static int bfs() {
        PriorityQueue<Pos> pq = new PriorityQueue<>();
        boolean[][] visited = new boolean[N][N];
        pq.offer(new Pos(0, 0, map[0][0]));	//초기값 PriorityQueue 저장
        visited[0][0] = true;	//초기 값 방문 확인
        //다익스트라 탐색 진행!
        while(!pq.isEmpty()) {
            Pos cur = pq.poll();
            if(cur.r == N-1 && cur.c == N-1)	//가장 먼저 (N-1, N-1) 도착시
                return cur.m;	//얻은 도둑 루피 반환
            //인접한 구역 탐색
            for(int i=0;i<4;i++) {
                int tempR = cur.r + dr[i];
                int tempC = cur.c + dc[i];
                if(inSpace(tempR,tempC) && !visited[tempR][tempC]) {
                    visited[tempR][tempC] = true;
                    pq.offer(new Pos(tempR,tempC, cur.m + map[tempR][tempC]));
                }
            }
        }
        return -1;
    }
    //이동하려는 칸이 동굴에 존재하는 영역인지 확인하는 함수
    static boolean inSpace(int r, int c) {
        if(r >= 0 && c>=0 && r < N && c < N)
            return true;
        return false;
    }
}