[백준] 1261 - 알고스팟

[문제링크]

1261번: 알고스팟

 

0. SWEA 보급로 문제의 열화판 (링크)

 

1. BFS를 이용해 1,1부터 N,M까지 탐색

 

* 1,1 노드부터 N,M노드까지 최소 거리를 구하는 다익스트라로 풀이 가능

  - 노드의 값 = 노드까지의 cost

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int M = pint(st.nextToken());
		int N = pint(st.nextToken());
		int[][] map = new int[N+2][M+2];
		int[][] cost = new int[N+2][M+2];
		
		//외곽설정, cost초기화
		for (int i = 0; i < N+2; i++) {
			map[i][0]=-1;map[i][M+1]=-1;
			Arrays.fill(cost[i], Integer.MAX_VALUE);
		}
		for (int i = 0; i < M+2; i++) {
			map[0][i]=-1;map[N+1][i]=-1;
		}
		
		//입력받기
		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i+1][j+1]=s.charAt(j)-'0';
			}
		}
		
		Queue<int[]> qu = new LinkedList<>();
		qu.offer(new int[] {1,1});
		cost[1][1]=0;
		
		while(!qu.isEmpty()) {
			int[]cur = qu.poll();
			int curCost = cost[cur[0]][cur[1]];
			//더 작은 코스트로 진행할 수 있다면
			for (int i = 0; i < 4; i++) {
				int tx=cur[0]+dx[i], ty=cur[1]+dy[i];
				
				if(map[ tx ][ ty ]!=-1 && curCost + map[ tx ][ ty ] < cost[ tx ][ ty ]) {
					qu.offer(new int[] {tx, ty});
					cost[ tx ][ ty ]=curCost+map[ tx ][ ty ];
				}
			}
		}
		System.out.println(cost[N][M]);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면