[백준] 6593 상범 빌딩 - BFS(너비우선탐색, 3차원, Three Dimension) JAVA

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

6593번: 상범 빌딩

코드설명

BFS(너비우선탐색, 3차원, Three Dimension) 를 활용하는 문제입니다.

 

코드로직은 다음과 같습니다.

1. 출발 지점('S')을 찾아 큐에 추가하고, BFS를 통해 최단 경로를 탐색합니다.
2. BFS 메서드에서는 큐(q)가 비어있을 때까지 루프를 돌면서 현재 위치에서 이동 가능한 모든 방향을 확인하고, 갈 수 있는 경우 큐에 새로운 위치를 추가합니다. 이때 방문 여부를 체크하여 중복 방문을 방지합니다.
3. 도착 지점('E')에 도달하면 해당 시간을 반환하고, 도착 지점에 도달하지 못하면 -1을 반환합니다.

 

문제에서 실수했었던 점은 다음과 같습니다.

// Queue<Node> q = new LinkedList<>(); //이렇게 처리하면 안된다. 전역적으로 처리하기 위해서는 아래와 같이 처리한다. 아예 새로 할 경우 새로운 자식 변수를 생성이 되는듯하다.
q = new LinkedList<>(); //이

 

여기서 q를 전역 변수로 선언하고 초기화하는 것이 중요한데, 만약 Queue<Node> q를 main 메서드 안에서 선언하면 해당 변수는 지역 변수가 되어 while 루프 내에서만 유효하게 됩니다. 따라서 새로운 반복문이 시작될 때마다 새로운 큐가 생성되기 때문에 이미 큐에 추가한 출발 지점('S')이 초기화되어 큐에 새로 들어가게 됩니다.

 

반면에 q를 전역 변수로 선언하면 while 루프 사이에서도 큐가 계속해서 유지됩니다. 따라서 이전에 큐에 추가한 출발 지점('S')이 그대로 남아 있게 되어 다음 루프에서 계속해서 BFS가 진행됩니다.

 

위에서 Queue<Node> q 로 초기화할경우 지역변수로 초기화됩니다.

아래와 같이 q = new LinkedList로 처리하여 전역변수로 유지합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int L, R, C;
	public static char[][][] map;
	public static int answer = 0;
	//동서남북상하
	public static int[] dx = {0, 0, 1, -1, 0, 0};
	public static int[] dy = {1, -1, 0, 0, 0, 0};
	public static int[] dz = {0, 0, 0, 0, 1, -1};
	public static Queue<Node> q;
	public static boolean[][][] visited;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());

    	while(true) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		L = Integer.parseInt(st.nextToken());
    		R = Integer.parseInt(st.nextToken());
    		C = Integer.parseInt(st.nextToken());
    		
    		if(L == 0 && R == 0 && C == 0) return ;
    			
    		map = new char[L][R][C];
    		visited = new boolean[L][R][C];
//    		Queue<Node> q = new LinkedList<>(); //이렇게 처리하면 안된다. 전역적으로 처리하기 위해서는 아래와 같이 처리한다. 아예 새로 할경우 새로운 자식변수를 생성이 되는듯하다.
    		q = new LinkedList<>(); //이
    		 
    		
    		for(int i=0;i<L;i++) {
    			for(int j=0;j<R;j++) {
    				st = new StringTokenizer(br.readLine());
    				String str = st.nextToken();
    				for(int k=0;k<C;k++) {
    					map[i][j][k] = str.charAt(k);
    					if(map[i][j][k] == 'S') {
    						q.offer(new Node(i, j, k, 0));
        					visited[i][j][k] = true;
    					}
    				}
    			}
    			st = new StringTokenizer(br.readLine());
    		}

//    		for(int i=0;i<L;i++) {
//    			for(int j=0;j<R;j++) {
//    				for(int k=0;k<C;k++) {
//    					System.out.print(" "+map[i][j][k]);
//    				}
//    				System.out.println();
//    			}
//    			System.out.println();
//    		}
    		
    		answer = BFS();
    		if(answer == -1){
    			System.out.println("Trapped!");
    		}else
    			System.out.println("Escaped in "+answer+" minute(s).");
    		
    	}
    	
    }
    
    public static int BFS() {
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		
    		if(map[temp.level][temp.r][temp.c] == 'E' ) {
    			return temp.cnt;
    		}
    		
    		for(int dir =0 ; dir < 6; dir++) {
    			int nl = temp.level + dz[dir];
    			int nr = temp.r + dx[dir];
    			int nc = temp.c + dy[dir];
    			
    			if(nl < 0 || nl >= L || nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
    			if(map[nl][nr][nc] == '#') continue;
    			if(visited[nl][nr][nc] == true) continue;
    			
    			visited[nl][nr][nc] = true;
    			q.offer(new Node(nl, nr, nc, temp.cnt + 1));
    		}
    		
    	}
    	
    	return -1;
    }
}

class Node{
	int level;
	int r;
	int c;
	int cnt = 0;
	public Node(int level, int r, int c, int cnt) {
		this.level = level;
		this.r=r;
		this.c=c;
		this.cnt = cnt;
	}
}