[백준BOJ] 1261번 알고스팟.java

 

백준 저지에서 알고스팟을 자바를 통해 풀어 보았다. 

 

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

1261번: 알고스팟

1261번 알고스팟.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

1261번 알고스팟 

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.
알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.
벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.
만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.
현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

설명

bfs를 통해 풀 수 있는 문제다.

 

벽을 최소한으로 부셔야한다. 따라서 방문 체크는 부신 벽의 수로 해야한다. 

 

bfs에서 큐에 삽입하는 조건으로 한 번도 방문하지 않았거나, 현재 부신 벽보다 적은 수의 벽을 부시고 도달한 것으로 둔다.

 

visit을 -1로 초기화할 수도 있겠지만 시간을 단축시키기 위해 최초 방문시 1로 초기화하고 최종적으로 출력할 때 -1을 해주었다.

코드

//1261번 알고스팟.java
package boj20211215;

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

public class 알고스팟_1261 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static class point{
    	int i;
    	int j;
    	point(int i, int j){
    		this.i=i;
    		this.j=j;
    	}
    }
    public static void main(String[] args) throws IOException {
		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];
		for(int i=1;i<=N;i++) {
			String line = br.readLine();
			for(int j=1;j<=M;j++) {
				map[i][j] = Integer.parseInt(line.substring(j-1,j));
			}
		}
		int[][] visit = new int[N+1][M+1];
		bfs(map, visit, N, M);
		System.out.println(visit[N][M]-1);
	}
    
    static void bfs(int[][] map, int[][] visit, int N, int M) {
    	int[] di = {0,0,1,-1};
    	int[] dj = {1,-1,0,0};
    	visit[1][1]=1;
    	Queue<point> q = new LinkedList<point>();
    	q.add(new point(1,1));
    	
    	while(!q.isEmpty()) {
    		point now = q.poll();
    		for(int d=0;d<4;d++) {
    			int i=now.i+di[d];
    			int j=now.j+dj[d];
    			if(1<=i&&i<=N&&1<=j&&j<=M) {
    				if(map[i][j]==0) {
    					if(visit[i][j]==0 || visit[i][j] > visit[now.i][now.j]) {
    						visit[i][j] = visit[now.i][now.j];
    						q.add(new point(i,j));
    					}
    				}
    				else if(map[i][j]==1) {
    					if(visit[i][j]==0 || visit[i][j] > visit[now.i][now.j]+1) {
    						visit[i][j] = visit[now.i][now.j]+1;
    						q.add(new point(i,j));
    					}
    				}
    			}
    		}
    	}
    	
    }
}