[1261] 알고스팟 - Java[자바]

 

| 문제 링크

 

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

 

 

 

---

 

 

 

| 문제

 

1. 첫째 줄에 N(열)과 M(행)이 주어집니다.
2. 그 다음 M줄에 줄마다 N개의 숫자가 들어옵니다.
   0(빈 칸) 또는 1(벽)
3. 1,1 부터 N,M 까지 이동하기까지 벽을 최소 몇 개 부수어야 하는지 출력하시오.

 

 

 

 

---

 

 

 

| 풀이

 

1. 맨 처음에는 일반적인 bfs에 사방 탐색으로 벽으로 막혀있는 경우에는 길을 뚫고 bfs를 이어갈 생각이었으나. 아래와 같은 반례에 막혀 데이크스트라(다익스트라라고도 불림)라는 알고리즘을 배우게 됐습니다.
   4 4
   0011
   1111
   0111
   0000
   answer : 1
   wrong answer : 2
2. 데이크스트라와 bfs의 차이점과 공통점은 다음과 같다.
   공통점: 너비 우선 탐색으로 최단 경로를 찾는데 주로 사용된다.
   차이점: bfs는 노드간 가중치가 없고(일반 Queue를 사용), 데이크스트라는 노드간 가중치를 두어(PriorityQueue를 사용) 가중치가 높은 너비를 우선 탐색한다.
3. 좌표와 가중치(벽을 한 번 부술 때 마다 가중치 +1)를 멤버 변수로 가지는 Node 클래스를 만들며, PriorityQueue(이하 pQue)에서 Node 값으로 정렬되기 위해 Comparable 인터페이스를 implements해줍니다.
4. 입력 받은 미로의 크기와 동일한 크기의 배열(weight)을 Integer.MAX_VALUE로 채우고 탐색하는 좌표의 가중치를 관리할 준비를 합니다.
5. 일반적인 bfs와 동일하게 1,1의 좌표 값과 가중치 0(첫 시작에는 빈 칸임을 문제에서 주어줌)을 pQue에 넣고 pQue가 공란이 될 때 까지 반복문을 동작합니다.
6. N,M 까지 너비 우선 탐색을 해주며, 벽(=1)을 만나는 경우 가중치를 +1 해주며 pQue에 넣고 weight 배열의 해당 좌표에 입력된 가중치보다 작은 경우 weight의 가중치를 해당 가중치로 바꿉니다.
7. 벽을 만나지 않는 경우에는 가중치를 증가시키지 않고 좌표와 함께 pQue에 넣어줍니다.
8. weight 배열의 N,M의 값을 출력합니다.

 

 

 

---

 

 

 

 

| 코드

 

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	public static int n;
	public static int m;
	public static int[][] maze;
	public static int[][] weight;
	public static int[][] delta = {{-1,0},{0,1},{1,0},{0,-1}};
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		maze = new int[m][n];
		weight = new int[m][n];
		for(int r = 0; r<m; r++) {
			String str = br.readLine();
			for(int c = 0; c<n; c++) {
				maze[r][c]=str.charAt(c)-'0';
				weight[r][c]=Integer.MAX_VALUE;
			}
		}
		if(n==1 && m==1)
			bw.write("0");
		else {
			dijkstra();
			bw.write(String.valueOf(weight[m-1][n-1]));
		}
		br.close();
		bw.close();
	}
	
	public static void dijkstra() {
		PriorityQueue<Node1261> pQue = new PriorityQueue<>();
		pQue.add(new Node1261(0,0,0));
		
		weight[0][0]=0;
		while(!pQue.isEmpty()) {
			Node1261 rc = pQue.poll();
			
			for(int i = 0; i<4; i++) {
				int dr = rc.r+delta[i][0];
				int dc = rc.c+delta[i][1];
				int wall = rc.wall;
				
				//인덱스의 범위를 벗어나는 경우 continue
				if(dr<0 || dr>=m || dc<0 || dc>=n)
					continue;
				if(maze[dr][dc]==1)
					wall++;
				if(weight[dr][dc]>wall) {
					weight[dr][dc] = wall;
					pQue.add(new Node1261(dr,dc,wall));
				}
				
			}
		}
	}
	//노드를 생성해 각 좌표를 관리하며, PriorityQueue에 넣기 위해 정렬 기준을 설정한다.
	public static class Node1261 implements Comparable<Node1261>{
		
		int r;
		int c;
		int wall;
		
		public Node1261(int r, int c, int wall) {
			super();
			this.r = r;
			this.c = c;
			this.wall = wall;
		}
		
		//Node1261끼리 정렬할 경우 wall 값의 오름차순으로 정렬
		public int compareTo(Node1261 o) {
			return this.wall-o.wall;
		}
		
	}

}