BOJ - 1261 ) 알고스팟

---

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

1261번: 알고스팟

---

1,1에서 N,M으로 벽을 최단개수로 부수면서 진행할 때에 몇개의 벽을 부수어야하는지 체크해주는 문제이다.

 

우선순위큐에 현재좌표와 몇개의 벽을 부수고 왔는지 체크해주면서 벽의 개수가 적은 순으로 정렬시킨다.

 

방문체크를 해주면서 1,1에서 N,M까지 진행시킨다. 4분탐색시에 갈곳이 1 이면 한개의 벽을 부수어야하므로

 

현재의 BROKE 값에 +1해주면서 진행한다.

 

---

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

public class 알고스팟 {
	public static class node{
		int y,x,broke;

		public node(int y, int x, int broke) {
			this.y = y;
			this.x = x;
			this.broke = broke;
		}
		
	}
	public static void main(String[] args) throws Exception {
		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());
		int map[][] = new int[n+1][m+1];
		boolean visit[][] = new boolean[n+1][m+1];
		for(int y= 1 ; y <=n ;y++) {
			char temp[] = br.readLine().toCharArray();
			for(int x = 1 ; x <= m ; x++) {
				if(temp[x-1]=='1') {
					map[y][x] =1;
				}
			}
		}
		PriorityQueue<node> pq = new PriorityQueue<>(new Comparator<node>() {
			public int compare(node o1, node o2) {
				if(o1.broke > o2.broke) return 1;
				else if(o1.broke == o2.broke) return 0;
				else return -1;
			};
		});
		
		pq.add(new node(1,1,0));
		visit[1][1]= true;
		
		int answer =0;
		int dir[][] = {{1,0},{-1,0}, {0,1}, {0,-1}};
		
		while(!pq.isEmpty()) {
				
			node now = pq.poll();
			int y = now.y;
			int x = now.x;
			int broke =  now.broke;
			if( y == n && x == m) {
				answer = broke;
				break;
			}
			for(int i = 0 ; i <4 ; i++) {
				int ny = y+ dir[i][0];
				int nx = x+ dir[i][1];
				if(ny > 0 && nx> 0 && ny <=n && nx<=m) {
					if(!visit[ny][nx]) {
						if(map[ny][nx]==1) {
							visit[ny][nx] = true;
							pq.add(new node(ny,nx,broke+1));
						}
						else if(map[ny][nx] ==0) {
							visit[ny][nx] = true;
							pq.add(new node(ny,nx,broke));
						}
					}
				}
			}
		}
		System.out.println(answer);
	}
}

---