백준 1584 - 게임

Java

1584 번 - 게임

문제

접근 방법

BFS를 통해 각 좌표를 이동하되, 다익스트라 개념을 사용하여 최단거리를 갱신하는 방법으로 500,500까지 도달한다.

코드

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

public class Main {
	static int n, result;
	static int MAX_VALUE = 999999999;
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("res/mainInput.txt"));	//제출 할 때 주석해야함
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    	StringTokenizer stk;
    	n = 501;
    	int[][] graph = new int[n][n];
    	int[][] dp = new int[n][n];
    	int m = stoi(br.readLine());

    	int[] yy = new int[2];
    	int[] xx = new int[2];
    	for(int idx = 0; idx < m; idx++) {
    		stk = new StringTokenizer(br.readLine());
    		yy[0] = stoi(stk.nextToken());
    		xx[0] = stoi(stk.nextToken());
    		yy[1] = stoi(stk.nextToken());
    		xx[1] = stoi(stk.nextToken());
    		Arrays.sort(yy);
    		Arrays.sort(xx);

    		for(int i = yy[0]; i <= yy[1]; i++) {
    			for(int j = xx[0]; j <= xx[1]; j++) {
    				graph[i][j] = 1;
    			}
    		}
    	}

    	m = stoi(br.readLine());
    	for(int idx = 0; idx < m; idx++) {
    		stk = new StringTokenizer(br.readLine());
    		yy[0] = stoi(stk.nextToken());
    		xx[0] = stoi(stk.nextToken());
    		yy[1] = stoi(stk.nextToken());
    		xx[1] = stoi(stk.nextToken());
    		Arrays.sort(yy);
    		Arrays.sort(xx);

    		for(int i = yy[0]; i <= yy[1]; i++) {
    			for(int j = xx[0]; j <= xx[1]; j++) {
    				graph[i][j] = -1;
    			}
    		}
    	}

    	// 0,0에서 500,500으로 가는 최단거리를 찾는다
    	for(int i = 0; i < n; i++) {
    		Arrays.fill(dp[i], MAX_VALUE);
    	}

    	// 상 하 좌 우
		int[] dy = {-1, 1, 0, 0};
		int[] dx = {0, 0, -1, 1};

		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] {0,0});
		dp[0][0] = 0;
		int[] q;
		int x,y,nx,ny;
		// BFS
		while(!queue.isEmpty()) {
			q = queue.poll();
			y = q[0];
			x = q[1];

			for(int i = 0; i < 4; i++) {
				ny = y + dy[i];
				nx = x + dx[i];

				if(isIn(ny,nx) && graph[ny][nx] != -1 && dp[ny][nx] > dp[y][x] + graph[ny][nx]) {
					dp[ny][nx] = dp[y][x] + graph[ny][nx];
					queue.add(new int[] {ny,nx});
				}
			}

		}
		if(dp[n-1][n-1] == MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(dp[n - 1][n - 1]);
    	br.close();
	}
	static boolean isIn(int y, int x) {
		if(0 <= y && y < n && 0 <= x && x < n)
			return true;
		return false;
	}
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점