[백준 23352번] 방탈출 - java

문제 설명

1. NxM크기의 격자판이 주어진다.

2. 상하좌우로 움직일 수 있으며, 각 방의 이동은 최단 경로로 움직인다.

3. 이렇게 최단 경로로 움직여서 가장 먼 거리를 움직이면, 그 시작점과 도착점이 비밀번호가 된다.

4. 가장 먼 거리가 여러개면 그 중 시작점과 도착점의 합이 큰 것이 비밀번호가 된다.

 

풀이 과정

 1. 최단 경로 -> BFS 그냥 공식처럼 외워서 진행하자. 

 2. 우리는 어디서부터 시작하는게 최고로 가까울지 모른다. 그러므로 모든 점에 대해 그곳부터 시작하는 경우를 싹 다 구해야 할 것이다. 

이 말은 완전탐색 + BFS로 진행해야 한다는 것이다.

 3. BFS를 통해 나아가면서, 해당 위치가 마지막인지 어떤지 모르므로 매번 거리를 재서 진행하는것이 속편할 것이다. 이는 BFS여서 쉽게 구할 수 있다.

 4. 알고리즘을 구현하면 다음과 같다.

A) 모든 점에 대해서 0이 아니면 해당 위치를 시작점으로 잡고 BFS시작 -> 당연히 이 모든 점에 대해서 BFS를 시작하기 전에 boolean을 초기화해주고, 해당 위치만 방문표시 해 줄 것이다.

B) 이동하면서 현재 이동거리가 최대 이동거리보다 많으면 그 최대 이동거리를 변경해주고, 현재위치가 도착점으로 판단해서 시작점+도착점을 ans로 저장해주면서 쭉쭉 이동한다.

C) 그리고 다시 상하좌우에서 갈 수 있는지 판단하여 이동하고 위의 내용을 다시 해주면 된다!!

 5. 난이도가 매우 높은 문제는 아니다. 다만 고려해야 할 사항이 함정처럼 있다....주의할것.

 6. 그리고 한가지 중요한것!! 방문체크는 상화좌우 판단시기에 해주자!! 아니면 큰일난다!!!

이건 매우 과장된 예시이긴 하지만... 이런 식으로 하나의 점에 대해 여러 Queue의 값에서 확인하고, 확인하고, 또 확인하는 코드가 돌아가게 된다.

이는 메모리 초과의 원인이 된다!!!!!

이렇게 강조하는 이유는 내가 실제로 그 메모리 초과에서 헤맸기 때문이다.

코드

	import java.util.*;
	class info{
	int x;
	int y;
	int move;
	info(int x, int y, int move){
	this.x = x;
	this.y = y;
	this.move = move;
	}
	}
	public class MyClass {
	public static int N, M;
	public static int map[][];
	public static boolean check[][];
	public static int start;
	public static int route = 0;
	public static int ans=0;
	public static int xMove[] = {-1, 1, 0, 0};
	public static int yMove[] = {0, 0, -1, 1};
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	N = sc.nextInt();
	M = sc.nextInt();
	map = new int[N][M];
	check = new boolean[N][M];
	for(int i=0; i<N; i++){
	for(int j=0; j<M; j++){
	map[i][j] = sc.nextInt();
	}
	}
	for(int i=0; i<N; i++){
	for(int j=0; j<M; j++){
	if(map[i][j] != 0){
	check = new boolean[N][M];
	check[i][j] = true;
	start = map[i][j];
	BFS(i, j);
	}
	}
	}
	System.out.println(ans);
	}
	public static void BFS(int xs, int ys){
	Queue<info> q = new LinkedList<>();
	q.add(new info(xs, ys, 0));
	while(!q.isEmpty()){
	info info = q.remove();
	int x = info.x;
	int y = info.y;
	int move = info.move;
	int end = map[x][y];
	if(move >= route){
	if(move > route){
	ans = start + end;
	}else{
	ans = Math.max(ans, start+end);
	}
	route = move;
	}
	for(int i=0; i<4; i++){
	int xTo = x + xMove[i];
	int yTo = y + yMove[i];
	if(xTo<0 || yTo<0 || xTo>=N || yTo>=M) continue;
	if(check[xTo][yTo] || map[xTo][yTo]==0) continue;
	check[xTo][yTo] = true;
	q.add(new info(xTo, yTo, move+1));
	}
	}
	}
	}

view raw 방탈출.java hosted with ❤ by GitHub