[백준] 4485 - 녹색 옷 입은 애가 젤다지?

[문제링크]

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

 

0. 가능한 적은 누적 숫자로 목표 지점에 도달하는 문제. BFS

 

1. 기본적인 큐를 이용한 BFS를 진행한다

 

2. cache 배열을 관리해, 어떠한 지점에 도달한 숫자의 최솟값을 저장한다

• 더 큰 숫자로 해당 지점에 도달한 경우, 더 이상 진행할 가치가 없다는 뜻. 소거한다
• cache 배열 초깃값은 문제 조건상 최댓값이 125*125*9 = 대략 14만이니, 그보다 큰 수 아무거나 입력한다

 

3. 어떤 지점에 같은 시점에 도달했을 경우, cache 배열이 여러번 갱신되며 큐에 같은 지점이 중복 삽입된다

• isCached boolean 배열을 관리해, 중복 삽입을 막는다
• Queue 기능을 하면서 Set인게 있나..? 있으면 좋을것같다

 

4. 모든 탐색이 끝난 후, 목표 지점인 [N][N] (배열 인덱스로는 [N-1][N-1]) 지점의 cache 값이 정답

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	static int[][] dir = {
		{1,0},{0,1},{-1,0},{0,-1}
	};
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int probCnt=1;
		while(true) {
			int N = pint(br.readLine());
			if(N==0)break;
            
			int[][]map = new int[N][N];
			int[][]cache = new int[N][N];
			boolean[][]isCached = new boolean[N][N];
			
			for (int i = 0; i < N; i++) {
				Arrays.fill(cache[i], 100000000);
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j]=pint(st.nextToken());
				}
			}
			
			Queue<int[]> qu = new LinkedList<int[]>();
			qu.offer(new int[] {0,0});
			isCached[0][0]=true;
			cache[0][0]=map[0][0];
			
			while(!qu.isEmpty()) {
				int[] cur = qu.poll();
				isCached[cur[0]][cur[1]]=false;
				
				for(int d=0; d<4; d++) {
					int nx = cur[0]+dir[d][0];
					int ny = cur[1]+dir[d][1];
					
					if(nx<0||nx>=N||ny<0||ny>=N)continue;
					
					if(cache[nx][ny] > map[nx][ny]+cache[cur[0]][cur[1]]) {
						cache[nx][ny] = map[nx][ny]+cache[cur[0]][cur[1]];
						if(!isCached[nx][ny]) {
							isCached[nx][ny]=true;
							qu.offer(new int[] {nx,ny});
						}
					}
				}
			}
			sb.append("Problem ").append(probCnt++).append(": ").append(cache[N-1][N-1]).append("\n");
			
		}
		System.out.println(sb);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면