[BAEKJOON_4485 - JAVA] 녹색 옷 입은 애가 젤다지?

문제

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

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

 

풀이

• 처음에는 DFS로 시도했으나 시간초과로 실패
  -> 다익스트라(dijkstra)를 활용.
  -> map[N][N]의 각 위치에 가기위한 가중치의 최솟값을 관리하는 것.
  -> 같은 크기의 dijk[N][N]에 해당 배열마다 도달하기 위한 가중치 값 저장.
  
  ex) (1,0)에 도착한 가중치가 dijk[1][0]에 저장된 가중치의 값보다 크다면 리턴,
       dijk[1][1]와 같이 인접행렬의 가중치는 (dijk[1][0] + map[1][1]) 혹은 (dijk[0][1] +map[1][1]) 처럼 값을
       더한 가중치를 비교 후 최소값을 저장.
• 우선순위 큐(PriorityQueue)를 사용한 다익스트라(dijkstra)
• 좌표와 값을 point 클래스를 통해 큐에 넣으며, 정렬을 위한 Comparable에서의 오름차순 정렬
• 다른 문제와 다르게 종료 조건이 N == 0 일 때이다.
  -> 출력문에 testcase의 번호가 출력되야 하기 때문에 반복횟수를 cnt로 관리.

 

 

사용한 알고리즘 지식

• 다익스트라
  -> 연습이 더 필요
• 우선순위 큐( Comparable 방법 )
  -> return 값에 따른 오름차순 내림차순.
• bufferedreader 닫는 습관이 필요.
  -> 알고리즘 풀이에 문제는 겪지 않았지만 닫는것이 바른 습관.

 

 

JAVA 코드

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

public class Main {

	// 좌표와 가중치 class
	static class point implements Comparable<point> {

		int row, col, cost;

		public point(int row, int col, int cost) {
			super();
			this.row = row;
			this.col = col;
			this.cost = cost;
		}

		@Override
		public int compareTo(point o) {
			return this.cost - o.cost; // 오름차순 정렬 ( return 값이 양수일때 자리바꿈 )
		}

	}

	static int N; // map의 크기, 최소루피값
	static int[][] map; // 입력 받는 map
	static int[][] dijk; // 최소비용을 저장
	static int[] dy = { 0, 1, -1, 0 }; // 우 하 상 좌
	static int[] dx = { 1, 0, 0, -1 };

	// 범위 검사
	static boolean isValid(int x, int y) {
		if (x < 0 || x >= N || y < 0 || y >= N)
			return false;
		return true;
	}

	public static int dijkstra() {
		PriorityQueue<point> pq = new PriorityQueue<point>();
		dijk[0][0] = map[0][0]; // 초기 값
		pq.offer(new point(0, 0, map[0][0])); // 시작 좌표

		while (!pq.isEmpty()) {
			point p = pq.poll();

			// 사방탐색
			for (int k = 0; k < 4; k++) {
				int nextRow = p.row + dy[k];
				int nextCol = p.col + dx[k];

				// 범위 검사
				if (isValid(nextRow, nextCol)) {
					if (dijk[nextRow][nextCol] > dijk[p.row][p.col] + map[nextRow][nextCol]) { // 기존의 가중치보다 작은 경우
						dijk[nextRow][nextCol] = dijk[p.row][p.col] + map[nextRow][nextCol]; // 가중치를 교환
						pq.offer(new point(nextRow, nextCol, dijk[nextRow][nextCol])); // 큐에 추가
					}
				}
			}
		}
		return dijk[N - 1][N - 1];
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		int cnt = 0; // 반복횟수
		while (true) {

			N = Integer.parseInt(br.readLine());
			if (N == 0) 
				break; 
			map = new int[N][N];
			dijk = 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());
					dijk[i][j] = Integer.MAX_VALUE;
				}

			} // end of input
			cnt++; // 반복 횟수 증가
			sb.append("Problem " + cnt + ": " + dijkstra() + "\n"); // 출력문
		}
		; // end of testcase;
		System.out.println(sb); // 출력
        br.close();
	}// end of main

}