[백준 1261] 알고스팟 (자바)

 

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

1261번: 알고스팟

난이도 : 골드 4

 

무난한 BFS 문제입니다. 

하지만 단순히 방문 여부로 목적지까지 길을 찾는다면 벽을 적게 부수며 멀리 돌아온 경우가

벽을 많이 부수며 빨리 도착한 경우에 밀려서 오답을 낼 수 있습니다.

방문하는 칸마다 최적화시켜서 목적지까지 찾아갔습니다.

---

전역 변수 

n, m = map의 크기(m이 가로 수, n이 세로 수)

map[][] = 미로의 값

value[][] = 각 칸까지 가기 위한 벽을 부순 횟수

dx [], dy [] = BFS 단골 상, 하, 좌, 우 탐색을 위한 배열

메소드

void main 

입력을 받습니다.(search 호출)

void search

Queue를 통해 BFS로 해결합니다.

x, y좌표를 갖는 qx, qy를 통해 상, 하, 좌, 우의 map의 값을 확인합니다.

value 값을 최적화 시키며 목적지까지 찾아갑니다.(check 호출)

boolean check

좌표값이 유효한 값인지 알려줍니다.

 

import java.io.*;
import java.util.*;

public class p1261 {
	static int n, m, map[][];
	static int value[][];
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		n = Integer.parseInt(stz.nextToken());
		m = Integer.parseInt(stz.nextToken());
		map = new int[m][n];
		value = new int[m][n];
		
		for(int i = 0; i < m; i++) {
			String s = br.readLine();
			Arrays.fill(value[i], Integer.MAX_VALUE);
			for(int j = 0; j < n; j++)
				map[i][j] = s.charAt(j)-'0';
		}
		
		search();
	}
	
	public static void search() {
		Queue<Integer> qx = new LinkedList<Integer>();
		Queue<Integer> qy = new LinkedList<Integer>();
		qx.add(0);
		qy.add(0);
		value[0][0] = 0;
		
		while(!qx.isEmpty()) {
			int x = qx.poll();
			int y = qy.poll();
			
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(check(nx, ny)) {
                	//map[nx][ny]가 벽이면서 방문하지 않았거나 방문 기록이 있지만 최적화 된 값이 아닐 때
                    //value[x][y] + 1로 값을 최적화 해줍니다.
					if(map[nx][ny] == 1 && (value[nx][ny] == Integer.MAX_VALUE || value[nx][ny] > value[x][y] + 1)) {
						value[nx][ny] = value[x][y] + 1;
						qx.add(nx);
						qy.add(ny);
					}
                    //map[nx][ny]가 벽이 아니고 방문하지 않았거나 방문 기록이 있지만 최적화 된 값이 아닐 때
                    //value[x][y]로 값을 최적화 해줍니다.
					else if(map[nx][ny] == 0 && (value[nx][ny] == Integer.MAX_VALUE || value[nx][ny] > value[x][y])) {
						value[nx][ny] = value[x][y];
						qx.add(nx);
						qy.add(ny);
					}
				}
			}
		}
		
		System.out.println(value[m-1][n-1]);
	}
	
	public static boolean check(int x, int y) {
		return x >= 0 && y >= 0 && x < m && y < n;
	}

}