관리 메뉴

공부공간

BOJ - 1261 ) 알고스팟 본문

그래프 알고리즘/Dijkstra

BOJ - 1261 ) 알고스팟

SangwonSeo 개발자가될수있을까? 2020. 4. 16. 11:08
728x90


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

 

1261번: 알고스팟

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다.

www.acmicpc.net


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);
	}
}

728x90

'그래프 알고리즘 > Dijkstra' 카테고리의 다른 글

BOJ - 10282 ) 해킹  (0) 2020.10.30
BOJ - 1167 ) 트리의 지름  (0) 2020.10.25
BOJ - 1504 ) 특정한 최단 경로  (0) 2020.08.24
BOJ - 1261 ) 알고스팟  (0) 2020.04.16
BOJ - 1916 ) 최소비용 구하기  (0) 2020.04.16
BOJ - 1753 ) 최단경로  (0) 2020.04.07
0 Comments
댓글쓰기 폼