[백준] 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 qu = new LinkedList(); 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("

"); } System.out.println(sb); } static int pint(String s) { return Integer.parseInt(s); } }

결과 화면

from http://nato-blog.tistory.com/156 by ccl(S) rewrite - 2021-11-27 02:28:12