[골드4] 4485. 녹색 옷 입은 애가 젤다지? (Java)

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

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

초록 옷이 젤다가 아니었다니,,,

---

※  문제를 요약하면 아래와 같습니다.

▶ 젤다는 잡혀있는 공주였따,,

▶ NxN 맵이 주어지고 각 칸에는 도둑루피가 존재

▶ 링크는 N-1, N-1 좌표에 최소한의 도둑루피를 목표로 이동

▶ N의 값이 0일 경우 탐색 종료

▶  Input : 첫째줄엔 N값 입력, 이후 N 줄에 N칸의 값이 입력

▶  Output : "Problem Testcase : 최소 루피값" 형태로 출력 

---

◈ Input - 1

3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4
0

◈ Output - 1

Problem 1: 20
Problem 2: 19
Problem 3: 36

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ NxN이차원 배열의 각 값을 가중치로 설정

▶ 맵은 상,하,좌우로 이동 가능 == 델타 탐색

▶ 최소 도둑루피 탐색 전 이차원 배열 => 노드 관계 설정

▶ 각 노드의 정보를 해당 노드의 도둑 루피 (black rupee) 와 다음 노드 번호를 저장 

▶ 노드들의 연결 관계를 델타 탐색을 활용하여 인접리스트 형태로 저장

▶ 다익스트라 알고리즘 활용 == 목표 지점까지 최소 가중치 값 찾기

    1. 노드의 크기만큼의 임의의 배열 narrBlack을 설정

      ( narrBlack == 목표 지점까지 각 노드의 최소 도둑루피를 들고 있는 값 == 각 노드에 도달하는 최소 가중치 값)

    2. 모든 배열 값을 Integer.max_value로 설정, 최초 탐색 번호인 0만 해당 배열의 값으로 설정

         (0번의 도둑루피 값을 들고 시작)

    3. 현재 narrBlack 값들 중 방문처리가 안되있으며 가장 작은 값을 찾은 후 해당 인덱스 저장

    4. 해당 인덱스는 방문 처리 ( == true로 설정)

    5. 해당 인덱스의 인접리스트를 탐색하여 연결된 노드들을 탐색

    6. narrBlack의 저장한 인덱스의 값+ 연결되어 있는 노드와의 가중치와 연결되어 있는 노드 번호의 narrBlack값을 비교하여 최소값 저장

    7. 3~6번을 모든 노드의 정보를 찾을 때 까지 반복

    8. narrBlack 배열의 N*N-1번째 값 == 최소 도둑루피의 값

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

class Node {
	int m_nEnd;
	int m_nBlack;

	public Node(int m_nEnd, int m_nBlack) {
		this.m_nEnd = m_nEnd;
		this.m_nBlack = m_nBlack;
	}

	@Override
	public String toString() {
		return "Node [m_nEnd=" + m_nEnd + ", m_nBlack=" + m_nBlack + "]";
	}
	
}

public class Main {
	static boolean[] barrVisited;
	static List<Node>[] listWay;
	static int[] narrBlack;
	static int N, M, nBetrayer, nMax, nOneCycle;
	static int[][] narrCave;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		N = 1;
		int nCount = 1;
		while (N != 0) {
			N = Integer.parseInt(bReader.readLine());
			if (N == 0)
				break;
			narrCave = new int[N][N];
			barrVisited = new boolean[N * N];
			narrBlack = new int[N * N];
			
			listWay = new LinkedList[N*N];
			
			for(int i = 0; i < N*N; i++)
				listWay[i] = new LinkedList<>();

			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(bReader.readLine());
				for (int j = 0; j < N; j++)
					narrCave[i][j] = Integer.parseInt(st.nextToken());
			}

			// 상, 하, 좌, 우 노드 관계 설정
			int nIndex = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (j + 1 < N)
						listWay[nIndex].add(new Node(nIndex + 1, narrCave[i][j + 1]));	// 동
					if (j - 1 >= 0)
						listWay[nIndex].add(new Node(nIndex - 1, narrCave[i][j - 1]));	// 서
					if (i + 1 < N)
						listWay[nIndex].add(new Node(nIndex + N, narrCave[i + 1][j]));	// 남
					if (i - 1 >= 0)
						listWay[nIndex].add(new Node(nIndex - N, narrCave[i - 1][j]));	// 북
					
					nIndex++;
				}
			}
			
			daijkstra(0);
			bWriter.write("Problem " + nCount + ": " + narrBlack[N*N-1] + "\n");
			nCount++;
			bWriter.flush();
		}

		bWriter.close();
	}

	public static void daijkstra(int nStart) {
		Arrays.fill(narrBlack, Integer.MAX_VALUE);
		narrBlack[0] = narrCave[0][0];
		
		for(int i =0; i < N*N; i++) {
			int nMin = Integer.MAX_VALUE;
			int nIndex = -1;
			
			// 최소 가중치를 갖는 노드 찾구
			for(int j = 0; j < N*N; j++) {
				if(!barrVisited[j] && nMin >= narrBlack[j]) {
					nMin = narrBlack[j];
					nIndex = j;
				}
			}
			
			if(nIndex == -1)
				break;
			
			barrVisited[nIndex] = true;
			for(int j = 0; j < listWay[nIndex].size(); j++) {
				Node curr = listWay[nIndex].get(j);
				
				if(barrVisited[curr.m_nEnd])
					continue;
				
				if(narrBlack[curr.m_nEnd] > narrBlack[nIndex] + curr.m_nBlack) {
					narrBlack[curr.m_nEnd] = narrBlack[nIndex] + curr.m_nBlack;
				}
			}
		}
		
	}
}

---

 

Good Luck! (피드백 감사합니다!)