[백준] G4 1261 알고스팟 (java)

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

1261번: 알고스팟

 

풀이

 

1) 입력 배열(map[][]), 방문체크 배열(isVisited[][]), 최단거리를 저장할 배열(distance[][]) 을 선언하고 distance는 무한대로 초기화한다.

2) 0,0 부터 시작하는 bfs 같은 dijstra 함수를 돌린다.

3) distance[0][0] 을 0으로 초기화. (시작지점이므로)

4) PriorityQueue를 사용해서 가장 짧은 노드 순서로 최단거리를 갱신한다.

5) 4방탐색을 하여 인접한 노드의 distance 를 갱신한다.

6) 다음 노드에 벽이 있든지 말든지 다음 노드까지 가는 최단거리는 현재노드 + map[nr][nc] 이다.

7) distance[N-1][M-1] 출력

 

주의사항

 

1) 경계가 넘지 않도록 주의한다.

2) 문제의 "(1, 1)과 (N, M)은 항상 뚫려있다." 가 없었다면 따로 체크를 해야하는 코드이다.

 

package com.baekJoon;

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

public class BJ_G4_1261_알고스팟 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,M,map[][],distance[][];
	static boolean isVisited[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		M = Integer.parseInt(tokens.nextToken());
		N = Integer.parseInt(tokens.nextToken());
		map = new int[N][M];
		distance = new int[N][M];
		isVisited = new boolean[N][M];
		for(int n=0; n<N; n++) {
			String line = input.readLine();
			for(int m=0; m<M; m++) {
				map[n][m] = line.charAt(m) - '0';
				distance[n][m] = Integer.MAX_VALUE;
			}	
		}
		dijkstra(0,0);
		System.out.println(distance[N-1][M-1]);
	}
	private static void dijkstra(int startI, int startJ) {
		distance[startI][startJ] = 0;
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(startI, startJ, 0));
		
		while(!pq.isEmpty()) {
			Node front = pq.poll();
			if(!isVisited[front.r][front.c]) {
				isVisited[front.r][front.c] = true;
				for(int d=0; d<4; d++) {
					int nr = front.r + dr[d];
					int nc = front.c + dc[d];
					if(isIn(nr, nc) && !isVisited[nr][nc] && distance[nr][nc] > distance[front.r][front.c] + map[front.r][front.c]) {
						distance[nr][nc] = distance[front.r][front.c] + map[front.r][front.c];
						pq.offer(new Node(nr, nc, distance[nr][nc]));
					}
				}
			}
		}
	}
	static class Node implements Comparable<Node>{
		int r;
		int c;
		int v;
		public Node(int r, int c, int v) {
			super();
			this.r = r;
			this.c = c;
			this.v = v;
		}
		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.v, o.v);
		}
		
	}
	static int dr[] = {0,0,-1,1};
	static int dc[] = {-1,1,0,0};
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<N && c<M);
	}
	static String src =
			"3 3\r\n" + 
			"011\r\n" + 
			"111\r\n" + 
			"110";
}

 

후기

 

 오늘 dijkstra문제를 5개정도 풀어서 자신감이 높아진 상태였는데 문제를 보자마자 못풀겠다는 생각이 들었다. ㅜㅜ

하지만 솔루션의 접근법 첫줄을 보자마자 이것도 다익스트라 문제라는것을 깨달았다. 많은 유형의 다익스트라 문제를 경험해서 실력을 키워야겠다. 더 노력하자.