시작점, 끝점이 주어질때 끝점으로 이동하면서 주어진 조건에 따라 최소값 또는 최댓값을 구하는 전형적인 BFS 문제이다.
시작점 : 0,0
끝점 : 500,500
문제의 조건 : 영역에 따라 0 또는 1을 더 하고 갈수 없는 지역이 존재
다음 영역에 대한 비용 Cost를 계산할때 안에 넣는 변수를 실수하지 않고 넣어줘야 한다. 현재지역변수와 다음지역변수를 헷갈리지 않아야한다.
예를들어 해당 문제에서는, 현재지역비용 + 다음지역으로 추가되는 비용 = 새로운 비용
식이 존재하는데 예를들면 이런실수를 하지 않도록 항상 "새로운 비용을 계산할떄는 2번확인하기"
// 새로운 비용 = 현재비용 + 다음지역 이동비용 (정상)
int newCost = value[cur.x][cur.y] + board[nx][ny];
// 새로운 비용 = 현재비용 + 현재지역 이동비용 (비정상) -> 코테망함
int newCost = value[cur.x][cur.y] + board[cur.x][cur.y];
처음에 BFS로 접근해야지 하고 DFS로 작성하고 있었다.
DFS의 경우 하나의 점에서 길 별로 500 * 500번 반복하게되므로 메모리가 남아나지 않게된다.
패턴이 일정해서 암기로 많이 외우고 코테때 빠르게 넘어가 시간을 많이 확보해야하는 유형이다.
import java.io.*;
import java.util.*;
public class Main {
static class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int[][] board ;
static int[][] value;
public static void main(String[] args) throws IOException {
board = new int[501][501];
value = new int[501][501];
for (int i = 0; i < 501; i++) {
for (int j = 0; j < 501; j++) {
value[i][j]= Integer.MAX_VALUE;
}
}
value[0][0]=0;
// init 필요 0,0 제외
// 위험지역
int N = Integer.parseInt(br.readLine());
setBoard(N, board, 1);
// 금지지역
int M = Integer.parseInt(br.readLine());
setBoard(M,board,2);
board[0][0]=0;
bfs(0,0);
if (value[500][500]==Integer.MAX_VALUE){
System.out.println(-1);
}
else {
System.out.println(value[500][500]);
}
}
public static void bfs(int startX, int startY){
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(startX,startY));
while (!queue.isEmpty()){
Node cur = queue.poll();
int[] dy = {1,-1,0,0};
int[] dx = {0,0,1,-1};
for (int i = 0; i < 4; i++) {
int ny = dy[i] + cur.y;
int nx = dx[i] + cur.x;
if (nx < 0 || nx > 500 || ny <0 || ny > 500){
continue;
}
if (board[nx][ny]==2){
continue;
}
// 현재 밸류 + 1
int newCost = value[cur.x][cur.y] + board[nx][ny];
if (value[nx][ny] > newCost){
value[nx][ny] = newCost; // 더 작은거
queue.add(new Node(nx,ny));
}
}
}
}
private static void setBoard(int N, int[][] board, int fill) throws IOException {
for (int i = 0; i < N; i++) {
String[] inp = br.readLine().split(" ");
int x1 = Integer.parseInt(inp[0]);
int y1 = Integer.parseInt(inp[1]);
int x2 = Integer.parseInt(inp[2]);
int y2 = Integer.parseInt(inp[3]);
// 항상 x1 y1이 작도록 변경
if (x1 > x2 ){
int tmp = x1;
x1 = x2;
x2 = tmp;
}
if (y1 > y2){
int tmp = y1;
y1 = y2;
y2 = tmp;
}
for (int x = x1; x <= x2; x++){
for (int y = y1; y <= y2; y++){
board[x][y] = fill;
}
}
}
}
}