[Java/자바 백준 4485] 녹색 옷 입은 애가 젤다지?

[Java/자바 백준 4485] 녹색 옷 입은 애가 젤다지?

반응형

풀이

최단 경로를 묻는 bfs 문제입니다

map에는 루피값을 넣어주고

check에 해당 경로까지 최솟값을 갱신해주면서 bfs를 풀었습니다.

아래처럼 방문한 적이 있든 없든, check에 해당 경로까지 최솟 값이 있으므로

조건을 줘서 다음경로까지의 거리합 > 현재 경로까지의 거리합 + 다음 경로 거리값 이면

큐에 넣어줬습니다.

if(check[nx][ny]>check[x][y]+map[nx][ny]) { check[nx][ny]=check[x][y]+map[nx][ny]; queue.offer(new int[] {nx,ny}); }

import java.io.*; import java.util.*; // bfs문제 check 현재 위치를 도달할 수 있는 최솟값을 갱신하면서 탐색 public class Main { static int[][] map, check; static Queue queue = new LinkedList(); static int[] dx= {1,0,-1,0}; static int[] dy= {0,1,0,-1}; static int n; public static void main(String[] args) throws Exception{ // TODO Auto-generated method stub BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st ; int tc=1; while(true) { n=Integer.parseInt(br.readLine()); map=new int[n][n]; check=new int[n][n]; if(n!=0) { for(int i=0; icheck[x][y]+map[nx][ny]) { check[nx][ny]=check[x][y]+map[nx][ny]; queue.offer(new int[] {nx,ny}); } } } } } }

728x90

반응형

from http://kwangkyun-world.tistory.com/79 by ccl(A) rewrite - 2021-09-29 14:01:33