[백준] 21736 헌내기는 친구가 필요해 - BFS(너비우선탐색) JAVA

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

코드설명

BFS(너비우선탐색) 를 활용합니다.

 

일반적인 BFS 문제로써, 4가지 방향을 고려하여 'X'일경우에는 멈추고, 다른 경우에는 계속해서 BFS를 진행합니다.

이 문제의 경우 물론 DFS로도 풀 수 있습니다. BFS가 이런 2차원 행렬에는 더 풀기 간단해보여서 BFS로 작성했습니다.

DFS로 풀경우, 하나의 첫 시작 DFS로 모든 맵을 순회할 것 입니다. 물론 방문처리로 갔던 곳은 다시 방문하지 않도록 합니다. (원상복구 하지 않습니다.)

코드

package Main;

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 {
	static int N, M, S, P, K, A, B, X;
	static int answer = 0;
	static char[][] matrix = new char[601][601];
	static int[] dx = {-1, 1, 0 , 0};
	static int[] dy = {0, 0, -1, 1};
	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());
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			matrix[i] = st.nextToken().toCharArray();
		}
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++){
				if(matrix[i][j] == 'I') {
					answer = BFS(i, j);
					if(answer == 0) System.out.println("TT");
					else System.out.println(answer);
					return ;
				}
			}
		}
	}
	
	static int BFS(int r, int c) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {r, c});
		boolean[][] visited = new boolean[N][M];
		visited[r][c] = true;
		
		int ret = 0;
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			
			if(matrix[temp[0]][temp[1]] == 'P') {
				ret += 1;
			}
			
			for(int dir =0 ; dir < 4; dir++) {
				int nr = temp[0] + dx[dir];
				int nc = temp[1] + dy[dir];
				if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
				if(visited[nr][nc] == true) continue;
				if(matrix[nr][nc] == 'X') continue;
				visited[nr][nc] = true;
				q.offer(new int[] {nr, nc});
			}
		}
		
		return ret;
	}
}