[백준] 1261번 / Java / 알고스팟

문제 - (www.acmicpc.net/problem/1261)

다익스트라 문제이다

---

📌주의할 점

• 내가 지금까지 시도해온 경로중에 최소가 되는 값을 저장해두는 배열이 필요하다. 코드에서는 brokens이라고 표현함
• 이 brokens배열은 MAX_VALUE로 초기화되어 있어야 함. (정답이 최소값을 구하는 문제이므로)
• bfs 메서드가 끝나고 나면 결국 우리가 구하고자 하는 답은 brokens배열의 가장 마지막번째에 존재함 (계속해서 기록해왔으므로)

---

😅실수

• 나는 이런식의 문제를 너무 dfs로 풀려고 한다.. 계속 파고드는 방식이므로 시간초과가 날 수밖에 없다! ~~를 어떻게 하는 최단 경로와 관련된 문제는 bfs로 접근하자
• 단 간선에 가중치가 있을 경우는 dfs, bfs를 고민해보아야 함

 

---

코드

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

public class Main {
	static int N;
	static int M;
	static char[][] map;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };
	static int[][] brokens;

	static class Point implements Comparable<Point> {
		int y;
		int x;
		int broken;

		public Point(int y, int x, int broken) {
			this.y = y;
			this.x = x;
			this.broken = broken;
		}

		@Override
		public int compareTo(Point o) {
			return Integer.compare(this.broken, o.broken);
		}

	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		brokens = new int[N][M];

		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
			Arrays.fill(brokens[i], Integer.MAX_VALUE);
		}

		bfs();
		System.out.println(brokens[N - 1][M - 1]);
	}

	private static void bfs() {
		PriorityQueue<Point> pq = new PriorityQueue<Point>();
		pq.offer(new Point(0, 0, map[0][0] - '0'));
		brokens[0][0] = map[0][0] - '0';

		while (!pq.isEmpty()) {

			Point cur = pq.poll();
			int y = cur.y;
			int x = cur.x;
			int cost = cur.broken;

			if (brokens[y][x] < cost)
				continue;

			for (int d = 0; d < 4; d++) {
				int ny = y + dy[d];
				int nx = x + dx[d];
				if (ny < 0 || nx < 0 || ny >= N || nx >= M)
					continue;
				if (brokens[ny][nx] > brokens[y][x] + (map[ny][nx] - '0')) {
					brokens[ny][nx] = brokens[y][x] + (map[ny][nx] - '0');
					pq.offer(new Point(ny, nx, brokens[ny][nx]));
				}
			}

		}

	}

}