1261 (다익스트라 문제)

알고스팟 : https://www.acmicpc.net/problem/1261

 

토론 : https://www.acmicpc.net/board/view/6593

 

dfs로 완탐하기에는 timeout으로 실패,

bfs하자니 0,1구분을 어떻게 해야할지 애매하고...

 

토론을 보니 다익스트라로 푸는 것이 쉽다는 아이디어 확인.

벽을 가중치 1짜리 그래프라 생각하고 0은 skip 하면서 aoj값이 작은 것 위주로 처리하면 결국 최단 통과로 N,M으로 도달하게 됨.

 

이문제의 진짜 함정은 입력이 M,N으로 주어진다는 것

 

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

public class Main {

	static int N, M;
	static int[][] graph;
	static boolean[][] visited;
	static int answer = Integer.MAX_VALUE;
	private static boolean DBG = false;

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

		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		graph = new int[N + 1][M + 1];
		visited = new boolean[N + 1][M + 1];
		for (int i = 1; i <= N; ++i) {
			char[] ca = br.readLine().toCharArray();
			for (int j = 1; j <= M; ++j) {
				graph[i][j] = ca[j - 1] - '0';
			}
		}

		for (int[] ar : graph) {
			for (int v : ar)
				System.out.print(v + " ");
			System.out.println();
		}

		// dfs(1,1,0);
		bfs();
	}

	private static void bfs() {
		PriorityQueue<Pos> Q = new PriorityQueue<>();
		Q.offer(new Pos(1, 1, 0));
		visited[1][1] = true;

		while (!Q.isEmpty()) {

			int size = Q.size();

			for (int q = 0; q < size; ++q) {
				Pos now = Q.poll();
				if (now.x == N && now.y == M) {
					System.out.println(now.aoj);
					return;
				}

				for (int i = 0; i < 4; ++i) {
					int nx = now.x + dx[i];
					int ny = now.y + dy[i];
					if (nx >= 1 && nx <= N && ny >= 1 && ny <= M && !visited[nx][ny]) {
						if (DBG)
							System.out.printf("[%d %d] %d\n", nx, ny, now.aoj);
						if (graph[nx][ny] == 0)
							Q.offer(new Pos(nx, ny, now.aoj));
						else
							Q.offer(new Pos(nx, ny, now.aoj + 1));
						visited[nx][ny] = true;
					}
				}

			}
		}
	}

	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };

	private static void dfs(int x, int y, int aoj) {
		if (aoj >= answer)
			return;

		if (visited[x][y])
			return;

		visited[x][y] = true;

		if (x == N && y == M) {
			answer = Math.min(answer, aoj);
		} else {
			for (int i = 0; i < 4; ++i) {

				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx >= 1 && nx <= N && ny >= 1 && ny <= M && !visited[nx][ny]) {
					if (graph[nx][ny] == 1) {
						dfs(nx, ny, aoj + 1);
					} else {
						dfs(nx, ny, aoj);
					}

				}
			}

		}

		visited[x][y] = false;
	}

}

class Pos implements Comparable<Pos> {
	int x, y, aoj;

	Pos(int x, int y, int aoj) {
		this.x = x;
		this.y = y;
		this.aoj = aoj;
	}

	@Override
	public int compareTo(Pos o) {
		return this.aoj - o.aoj;
	}
}