[백준 1261 - JAVA] 알고스팟

1261번: 알고스팟

 

풀이 방향을 맞게 잡았으나 조건을 잘못 넣어서 메모리 초과가 2번 났었다.

다익스트라인줄 몰랐으나 풀고보니 최소 횟수를 따라가며 갱신할 수 있을 때 큐에 삽입하는 다익스트라 방식으로 잘 풀었었다ㅎㅎ...

 

풀이 방법

1. 벽을 뚫은 횟수(이하 cnt)를 저장할 2차원 배열(ans) 을 생성하고 큰값으로 초기화한다.

2. 초기 장소인 0, 0 cnt는 0으로 배열을 만들어 cnt가 기준인 우선순위큐에 넣는다. 
   * 처음 장소는 항상 뚫려있다.

3. 큐가 빌때까지 bfs를 수행하는데 아래 조건을 충족한다.

   1. 벽을 만날 경우 cnt를 1 증가시킨다.

   2. cnt가 ans에 저장된 횟수보다 작을 경우만 큐에 삽입한다.

 

 

import java.io.*;
import java.util.*;

public class Main {
	public static final int INF = Integer.MAX_VALUE/2;
	public static int N, M;
	public static int[][] map;
	public static int[][] ans;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	
	public static void bfs() {
		PriorityQueue<int[]> que = new PriorityQueue<int[]>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o1[2], o2[2]);
			}
		});
		que.add(new int[] {0, 0, 0});
		ans[0][0] = 0;
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			
			if (cur[2] > ans[cur[0]][cur[1]]) continue;
			for (int i = 0; i < 4; i++) {
				int nx = cur[0] + dx[i];
				int ny = cur[1] + dy[i];
				if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
				int cnt = cur[2];
				if (map[nx][ny] == 1) cnt++;
				if (ans[nx][ny] > cnt) {
					ans[nx][ny] = cnt;
					que.add(new int[] {nx, ny, cnt});
				}
			}
		}
	}
	
	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 int[N][M];
		ans = new int[N][M];
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = line.charAt(j)-'0';
			}
		}
		for (int[] arr : ans) {
			Arrays.fill(arr, INF);
		}
		bfs();
		System.out.println(ans[N-1][M-1]);
	}
}