[백준] 16920 확장 게임 - BFS(너비우선탐색) JAVA

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

16920번: 확장 게임

코드설명

BFS(너비우선탐색) 를 활용하는 문제입니다.

 

문제에 대한 접근방식을 올바르게 접근해야합니다.

문제에서 가장 중요한점은, 각 이동방향을 "동시에" 처리해야하고, "동시에" 처리하기 위해서는 같은 이동사이클에서 다른 이동에 영향을 받지 않아야 합니다. 또한, 확장시 해당 범위 내에서 2칸의 모든 공간을 의미한다는점 또한 유의하여 각 이동을 처리해줍니다. 

이를 위해 Queue[] 에서 처리하는것이라고 이해하면 도움이 될 것 입니다.

만약, PriorityQueue를 이용할경우 같은 이동사이클내에서 이동처리하는것이 불가합니다.

 

처음에 풀었던 코드는 PriorityQueue로 각 성의 숫자를 넣고서 BFS를 진행했습니다.

이떄 우선순위는 숫자가 낮을수록, 즉 1번성부터 움직이게 처리했습니다.

 

하지만, 이때 문제가 발생합니다.

각 성이 확장할때 성은 그 주변의 모든 거리 2에 해당하는 공간을 확장합니다.

문제에서는 직접적으로 그렇게 표현되어있지 않아, 입력예시 5번을 보고 깨닳았습니다. 

(입력에시 5번이 이해 안갈경우, https://www.acmicpc.net/board/view/35314 )

 

또한 PriorityQueue를 사용하지않고, Queue[] 처리 방식으로 진행해야하는 이유는

https://www.acmicpc.net/board/view/35413

글 읽기 - 큐 처리 방식의 차이가 궁금합니다..ㅠ

위의 답변글을 보면 이해할 수 있습니다.

 

간단한 BFS 코드로직입니다.

• BFS() 메서드에서 각 사람의 이동을 BFS로 처리합니다.
• dx와 dy 배열은 상하좌우 이동을 나타냅니다.
• flag 변수는 모든 사람이 더 이상 이동할 수 없을 때까지 반복을 제어합니다.
  • 이 부분에서 모든 Queue[] 를 확인하며 QSize가 0 이 하나도 없는경우로 처리해도되지만, 빠른 처리를 위해 flag로 한번도 Queue에 넣지 않는다면 종료시킵니다.
• while (!flag) 루프를 통해 모든 사람에 대한 BFS를 반복합니다.

코드

Queue[] 배열을 활용하여 진행합니다.

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

public class Main {
	public static int N, M, P;
	public static char[][] map;
	public static int[] S;
	public static Queue<Node>[] q;
	public static boolean[][] visited;
	public static int[] answerCnt = new int[10];
    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());
    	P = Integer.parseInt(st.nextToken());
    	map = new char[N][M];
    	q = new Queue[P + 1];
    	for(int i=0;i<=P;i++) {
    		q[i] = new LinkedList<Node>();
    	}
    	st = new StringTokenizer(br.readLine());
    	S = new int[P+1];
    	for(int i=1;i<P+1;i++) {
    		S[i] = Integer.parseInt(st.nextToken());
    	}
    
    	visited = new boolean[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());	
			map[i] = st.nextToken().toCharArray();
			for(int j=0;j<M;j++) {
				if(map[i][j] >= '1' && map[i][j] <= '9') {
					visited[i][j] = true;
					q[map[i][j] - '0'].offer(new Node(i, j));
					answerCnt[map[i][j] - '0'] += 1;
				}
			}
    	}
    	
    	BFS();
    	
    	for(int i=1; i<=P; i++) {
    		System.out.print(answerCnt[i]+" ");
    	}
    }
    public static void BFS() {
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	
    	boolean flag = false;
    	while(!flag) {
    		flag = true;
    		for(int people=1; people<=P; people++) {
    			int moveCnt = S[people];
    			int qSize = q[people].size();
    			int cnt = 0;
    			int cycleCnt = 0;
    			while( !q[people].isEmpty() && cycleCnt < moveCnt) {
    				Node temp = q[ people].poll();
    				for(int dir = 0; dir < 4; dir++) {
    					int nr = temp.r + dx[dir];
    					int nc = temp.c + dy[dir];
    					
    					if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
    					if(visited[nr][nc] == true) continue;
    					if(map[nr][nc] == '#') continue;
    					visited[nr][nc] = true;
    					answerCnt[people] += 1;
    					flag = false;
    					q[people].offer(new Node(nr, nc));
    				}
    				cnt += 1;
    				
    				if(qSize == cnt) {
    					qSize = q[people].size();
    					cnt = 0;
    					cycleCnt += 1;
    				}
    			}
    			
////    			System.out.println("========================");
//    			for(int i=0;i<=P;i++) {
//    				System.out.print(" "+answerCnt[i]);
//    			}
//    			System.out.println();
    			
    		}
    		
    		
    		
    	}
    	
    }
    
    
}

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

 

PriorityQueue를 활용할경우, 먼저 탐색한 공간에 접근하지 못해 올바르게 확장되지 못합니다.

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

public class Main {
	public static int N, M, P;
	public static char[][] map;
	public static int[] S;
	public static PriorityQueue<Node> pq = new PriorityQueue<>();
	public static boolean[][] visited;
	public static int[] answerCnt = new int[10];
    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());
    	P = Integer.parseInt(st.nextToken());
    	map = new char[N][M];
    	
    	st = new StringTokenizer(br.readLine());
    	S = new int[P+1];
    	for(int i=1;i<P+1;i++) {
    		S[i] = Integer.parseInt(st.nextToken());
    	}
    
    	visited = new boolean[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());	
			map[i] = st.nextToken().toCharArray();
			
			for(int j=0;j<M;j++) {
				if(map[i][j] >= '1' && map[i][j] <= '9') {
					visited[i][j] = true;
					pq.offer(new Node(i, j, map[i][j] - '0'));
					answerCnt[map[i][j] - '0'] += 1;
				}
			}
    	}
    	
    	BFS();
    	
    	for(int i=1; i<=P; i++) {
    		System.out.print(answerCnt[i]+" ");
    	}
    }
    public static void BFS() {
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	PriorityQueue<Node> newPq = new PriorityQueue<>();
    	
    	int pqSize = pq.size();
    	int cnt = 0;
    	while(!pq.isEmpty()) {
    		Node temp = pq.poll();
//    		System.out.println("============");
//    		System.out.println(temp.r+" "+temp.c+" "+temp.idx);
    		
    		for(int dir = 0; dir < 4; dir++) {
    			int moveCnt = S[temp.idx];
    			int nr = temp.r;
    			int nc = temp.c;
    			
    			while(--moveCnt >= 0) {
        			nr += dx[dir];
        			nc += dy[dir];
        			
        			if(nr < 0 || nr >= N || nc < 0 || nc >= M) break;
        			if(map[nr][nc] == '#') break;
        			if(visited[nr][nc] == true) break;
        			answerCnt[temp.idx] += 1; 
        			visited[nr][nc] = true;
//        			System.out.println("nr:"+nr+ "nc:"+nc);
//        			pq.offer(new Node(nr, nc, temp.idx));
        			newPq.offer(new Node(nr, nc, temp.idx));
    			}
    		}
    		
    		cnt += 1;
    		if(pqSize == cnt) {
    			pqSize = newPq.size();
    			cnt = 0;
    			pq = newPq;
    			newPq = new PriorityQueue<>();
    		}
    		
    		
    	}
    	
    }
    
    
}

class Node implements Comparable<Node>{
	int r;
	int c;
	int idx;
	public Node(int r, int c, int idx) {
		this.r=r;
		this.c=c;
		this.idx=idx;
	}
	@Override
	public int compareTo(Node other) {
		if(this.idx > other.idx) {
			return 1;
		}else if(this.idx == other.idx){
			return 0;
		}else {
			return -1;
		}
	}
}