공부공간

BOJ - 1584 ) 게임 본문

알고리즘/완전탐색(BFS,DFS)

BOJ - 1584 ) 게임

개발자가될수있을까? 2021. 10. 17. 22:17


 

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

 

1584번: 게임

첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의

www.acmicpc.net

 

 


전형적인 0-1 BFS의 문제이다. 죽음의 구역은 못가기때문에, BFS를 돌릴때에 방문한거와 동일하게 처리해준다.

 

이동할때에, 위험한 구역에 들어가면 1의 가중치가 소요되므로 이경우에는 덱의 맨뒤에 넣고

 

안전한 구역은 덱의 맨앞에넣어서 탐색을 계속 진행한다. 

 

(500,500)에 도달했다면, 최솟값이 보장되기때문에 출력을 진행하면된다.

 

 

 


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class BOJ_1584 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		ArrayDeque<int[]> dq = new ArrayDeque<>();
		
		int maxsize = 501;
		
		boolean warning[][] = new boolean[maxsize][maxsize];
		boolean visit[][] = new boolean[maxsize][maxsize];
		int m =  Integer.parseInt(st.nextToken());
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			int temp = -1;
			if(x1>x2) {temp = x1;x1 = x2 ;x2 = temp;}
			if(y1>y2) {temp = y1;y1 = y2 ;y2 = temp;}
			for(int j=x1;j<=x2;j++) {
				for(int j2=y1;j2<=y2;j2++) {
					warning[j][j2] = true;
				}
			}
		}
		int n = Integer.parseInt(br.readLine());
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			int temp = -1;
			if(x1>x2) {temp = x1;x1 = x2 ;x2 = temp;}
			if(y1>y2) {temp = y1;y1 = y2 ;y2 = temp;}
			for(int j=x1;j<=x2;j++) {
				for(int j2=y1;j2<=y2;j2++) {
					visit[j][j2] = true;
				}
			}
		}

			
		int answer = -1;
		int dir[][] = {{1,0},{-1,0},{0,-1},{0,1}};
		warning[0][0] = false; visit[0][0] = true;
		dq.add(new int[] {0,0,0});
		while(!dq.isEmpty()) {
			int now[] = dq.poll();
			if(now[0]==500&&now[1]==500) {
				answer =now[2];
				break;
			}
			for(int i=0;i<4;i++) {
				int ny = now[0] + dir[i][0];
				int nx = now[1] + dir[i][1];
				if(ny>=0&&nx>=0&&ny<=500&&nx<=500) {
					if(!visit[ny][nx]) {
						if(warning[ny][nx]) {
							dq.addLast(new int[] {ny,nx,now[2]+1});
						} else {
							dq.addFirst(new int[] {ny,nx,now[2]});
						}
						visit[ny][nx] = true;
					}
				}
			}
		}
		System.out.println(answer);
	}
}

'알고리즘 > 완전탐색(BFS,DFS)' 카테고리의 다른 글

BOJ - 23747 ) 와드  (0) 2022.01.25
BOJ - 13463 ) Brexit  (0) 2022.01.19
BOJ - 5014 ) 스타트링크  (0) 2021.08.21
BOJ - 15812 ) 침략자 진아  (0) 2021.05.13
BOJ - 9205 ) 맥주 마시면서 걸어가기  (0) 2020.11.26
Comments