[백준] 3055 탈출 - BFS JAVA

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

3055번: 탈출

코드설명

BFS 문제입니다.

 

문제에서 유의해야할점들입니다.

1. 물이 여러개 주어질 수 있습니다. (처음에 물이 무조건 1개만 주어지는줄알고 코딩했습니다.)

2. Queue의 얕은복사와 깊은복사.

처음에 아래와 같이 진행하며 Queue가 자동으로 깊은복사가 되는 줄 알았지만
얕은복사가 되어 주소값을 참조하게 됩니다. 그럴경우에 둘이 같은 주소값을 가리키게 되면서 당연히 작동하지 않습니다.
waterQ = newWaterQ.; 얕은복사로 이후에 pop되면서 사라집니다..
gosumdochiQ = newGosumdochiQ;


그대신 아래와 같이 진행합니다.
while(!newWaterQ.isEmpty()) {
    waterQ.add(newWaterQ.poll());
}
while(!newGosumdochiQ.isEmpty()) {
    gosumdochiQ.add(newGosumdochiQ.poll());
}


//
처음에 아예 생각을 잘못하고
for(Node a : newGosumdochiQ) {
    gosumdochiQ.add(a);
}
Queue를 단순 순회하여 실수했었습니다.

3. 현재 따로 newQueue를 선언하여 진행하지만, int currentLength = q.size() 를 통해서 굳이 새로운 newQueue를 선언하지 않고 진행하는 방법도 있습니다.

메모리사용면에서 위의 size 방식을 사용하는것이 나을것 같습니다.

 

4. '*'는  여러개일 수 있습니다. 혹은 없을 수도 있습니다.

public static Node gosumdochiNode = null, waterNode = null;
를 선언하여 q.add(waterNode)를 진행했었는데 이럴경우에 물이 없는경우 null값이 들어가지만
q.size()는 똑같이 1 입니다. 이유는 waterNode가 null 안상태로 들어갔기에 Queue를 활용하면 nullPoitnerException이 나오기에

아래와 같이 만날떄마다 넣는것으로 수정하였습니다.
이러한 오류가 발생한 이유는 'S'와 '*'가 무조건 1개일것이라고 생각하여서 발생한 문제입니다.
문제를 잘읽고 풀어야합니다.
for(int i=0;i<N;i++) {
    for(int j=0;j<M;j++) {
        if(map[i][j] == 'S') { //고슫도치의 위치
            gosumdochiQ.add(new Node(i,j));
        }
        else if(map[i][j] == '*') { //물의 위치
            waterQ.add(new Node(i,j));
        }
    }
}

 

10 11
D..........
...........
...........
...........
...........
...........
........S..
...........
...........
...........
14

테스트케이스 도움받은글 https://www.acmicpc.net/board/view/27210

 

코드

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 N, M;
	public static char[][] map;
	public static int[] dx= {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int answer=0;
//	public static Node gosumdochiNode = null, waterNode = null;
	public static Queue<Node> waterQ = new LinkedList<Node>();
	public static Queue<Node> gosumdochiQ = new LinkedList<Node>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	map = new char[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(map[i][j] == 'S') { //고슫도치의 위치
    				gosumdochiQ.add(new Node(i,j));
    			}
    			else if(map[i][j] == '*') { //물의 위치
    				waterQ.add(new Node(i,j));
    			}
    		}
    	}

    	simulate();
    	if(answer == 0) {
    		System.out.println("KAKTUS");
    	}else {
    		System.out.println(answer);	
    	}
    	
    	
    }
    
    public static void simulate() {

    	
    	Queue<Node> newWaterQ = new LinkedList<Node>();
    	Queue<Node> newGosumdochiQ = new LinkedList<Node>();
    	
    	
    	int time =0 ;
    	while(true) {
    		time += 1;
    		if(gosumdochiQ.isEmpty()) {
    			return ; //만약 더이상 고슴도치에 큐가 없다면 고슴도치가 없는것이므로 실패임.
    		}
    		
    		while(!waterQ.isEmpty()) {
    			Node temp = waterQ.poll();
    			int r = temp.r;
    			int c = temp.c;
    			for(int dir=0;dir<4;dir++) {
    				int nr = r + dx[dir];
    				int nc = c + dy[dir];
    				
    				if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
    				if(map[nr][nc] != '.') continue;
    				map[nr][nc] = '*';
    				newWaterQ.add(new Node(nr, nc));
    			}
    		}
    		
    		
    		while(!gosumdochiQ.isEmpty()) {
    			Node temp = gosumdochiQ.poll();
    			int r = temp.r;
    			int c = temp.c;
    			
    			for(int dir=0;dir<4;dir++) {
    				int nr = r + dx[dir];
    				int nc = c + dy[dir];
    				
    				if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
    				if(map[nr][nc] == 'S') continue;
    				if(map[nr][nc] == 'X' || map[nr][nc] =='*') continue; //물은 '벽'과 '굴'로 이동할 수 없음
    				if(map[nr][nc] == 'D') {
    					answer = time;
    					return ;
    				}
    				
    				map[nr][nc] = 'S';
    				newGosumdochiQ.add(new Node(nr, nc));

    			}
    		}
    		

    		while(!newWaterQ.isEmpty()) {
    			waterQ.add(newWaterQ.poll());
    		}
    		while(!newGosumdochiQ.isEmpty()) {
    			gosumdochiQ.add(newGosumdochiQ.poll());
    		}
    	}
    	
    }
    
}

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