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

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

문제

문제 링크

접근 방식

1. 2차원 배열을 탐색한다
2. 행 * M + 열 을 정점번호로 할당한다
3. 현재 정점에서부터 4방 탐색한 후, 탐색한 정점에서 현재 정점으로의 가중치를 현재 정점이 1이면 1, 0이면 0을 준다
4. 다익스트라 알고리즘으로 0번 정점부터 M-1번 까지의 최소 거리를 구한다

코드

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

public class Main_1261 {

	public static class Vertex implements Comparable<Vertex>{
		int no;
		int w;
		
		Vertex(int no, int w){
			super();
			this.no = no;
			this.w = w;
		}

		@Override
		public int compareTo(Vertex o) {
			return this.w - o.w;
		}	

	}
	
	static int[][] deltas = {{-1,0},{0,1},{1,0},{0,-1}};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Vertex>> list = new ArrayList<>();
		for(int i=0;i<N*M;i++) {
			list.add(new ArrayList<>());
		}
		
		for(int i=0;i<N;i++) {
			String line = br.readLine();
			for(int j=0;j<M;j++) {
				int data = line.charAt(j) - '0';
				
				
				for(int k=0;k<4;k++) {
					int nextI = i+deltas[k][0];
					int nextJ = j+deltas[k][1];
					
					if(nextI < 0 || nextI >= N || nextJ < 0 || nextJ >= M) continue;
					if(data == 0) list.get(nextI*M + nextJ).add(new Vertex(i*M + j,0));
					else list.get(nextI*M + nextJ).add(new Vertex(i*M + j,1));
				}
			}
		}
		
		int[] distance = new int[N*M];
		boolean[] visited = new boolean[N*M];
		
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		int start = 0;
		distance[start] = 0;
		PriorityQueue<Vertex> pq = new PriorityQueue<>();
		pq.offer(new Vertex(start,distance[start]));
		
		while(!pq.isEmpty()) {
			int current = pq.poll().no;
			
			if(visited[current]) continue;
			
			if(current == N*M-1) {
				System.out.println(distance[current]);
				break;
			}
			
			for(Vertex v : list.get(current)) {
				if(distance[v.no] > distance[current] + v.w) {
					distance[v.no]= distance[current] + v.w;
					pq.offer(new Vertex(v.no,distance[v.no]));
				}
			}
		}
		
				
	}

}