4485. 녹색 옷을 입은 애가 젤다지? (Java)

2023. 10. 11. 17:16·Algorithm & Data Structures/BOJ

다익스트라의 개념을 알수 있는 문제다.

다익스트라는 BFS에서 Queue를 사용하지만 Compareable과 priority queue를 사용하여  
BFS 처럼 모든 경우를 보는 것이 아닌 가중치가 최저인 값을 우선적으로 확인한다. 
고로 BFS보다 빠른 것으로 나타난다.

음의 가중치일때는 사용할 수 없으며 출발점과 도착점이 정해진 경우에 사용가능한 

다익스트라 알고리즘 이었다.

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


public class b4485{
	static class Node implements Comparable<Node>{
		int x, y, w;

		public Node(int x, int y, int w) {
			super();
			this.x = x;
			this.y = y;
			this.w = w;
		}
		
		public int compareTo(Node o) {
			return this.w-o.w;
		}
	}
	
	static int N;
	static int[][] map;
	static int[][] dijk;
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	
	public static boolean isValid(int nx, int ny) {
		if(nx>=0 && nx<N && ny>=0 && ny<N)
			return true;
		return false;
	}
	public static int dijkstra()  {
		PriorityQueue<Node> q = new PriorityQueue<>(); 
		dijk[0][0] = map[0][0];
		q.offer(new Node(0,0,map[0][0]));
		
		while(!q.isEmpty()) {
			if(dijk[N-1][N-1]!=Integer.MAX_VALUE) break;
			Node p = q.poll();
			for(int d = 0 ; d < 4 ; d++) {
				int nx = p.x+dx[d];
				int ny = p.y+dy[d];
				if(isValid(nx,ny)) {
					if(dijk[nx][ny]>dijk[p.x][p.y]+map[nx][ny]) {
						dijk[nx][ny] = dijk[p.x][p.y]+ map[nx][ny];
						q.offer(new Node(nx,ny,dijk[nx][ny]));
					}
				}
			}
		}
				
		return dijk[N-1][N-1];
	}
	
	public static void main(String[] args) throws IOException{
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int cnt = 0;
		
		while(true) {
			N = Integer.parseInt(br.readLine());
			if(N==0) break;
			cnt++;
			map = new int[N][N];
			dijk = new int[N][N];
			for(int i = 0 ; i < N ; i++) {
				StringTokenizer 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;
				}
			}
			System.out.println("Problem "+cnt+": "+dijkstra());
		}
	}
}

 

'Algorithm & Data Structures > BOJ' 카테고리의 다른 글

13549. 숨바꼭질3 (Java)  (0) 2023.10.17
2206. 벽부수고 이동하기 (Java)  (0) 2023.10.16
11404. 플로이드 (Java)  (0) 2023.10.12
9465. 스티커 (Java)  (1) 2023.10.12
17144. 미세먼지 안녕! (Java)  (2) 2023.10.11
'Algorithm & Data Structures/BOJ' 카테고리의 다른 글
  • 2206. 벽부수고 이동하기 (Java)
  • 11404. 플로이드 (Java)
  • 9465. 스티커 (Java)
  • 17144. 미세먼지 안녕! (Java)
Geisha
Geisha
개발 일기
  • Geisha
    Geisha
    Geisha
  • 전체
    오늘
    어제
    • 분류 전체보기 (335)
      • Algorithm & Data Structures (253)
        • BOJ (111)
        • SWEA (1)
        • Programers (137)
        • Data Structures (3)
      • DB (29)
        • SQL (23)
        • RDBMS (2)
      • Java (1)
        • Class (1)
      • Spring (5)
        • Spring MVC (1)
        • Annotations (1)
      • CS (36)
        • 운영체제 (13)
        • 네트워크 (5)
      • Tool (6)
        • Git (5)
        • AWS (1)
      • Project (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    binarySearch
    동적계획법
    구현
    baekjoon
    DynamicProgramming
    Union-Find
    다익스트라
    algorithm
    자바
    경로압축
    투포인터
    백준
    Stack
    유니온파인드
    dfs
    이분탐색
    프로그래머스
    BFS
    SQL
    Java
    스택
    전위순회
    후위순회
    dp
    골드
    알고리즘
    Dijkstra
    PriorityQueue
    백트래킹
    programmers
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
Geisha
4485. 녹색 옷을 입은 애가 젤다지? (Java)
상단으로

티스토리툴바