백준 21736 헌내기는 친구가 필요해 (Java)

1. 문제 링크

21736번: 헌내기는 친구가 필요해

 

2. 문제 및 입출력예제

 

3. 문제 풀이

BFS를 이용하여 벽이 아닌 공간을 전부 방문한다.

P가 나올 경우 결과값을 1씩 더한다.

갈 수 있는 공간을 전부 가면 끝낸다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.io.IOException;

public class Main {
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int dx[] = {0,0,-1,1};
		int dy[] = {-1,1,0,0};
		String[] split = br.readLine().split(" ");
		int N = Integer.parseInt(split[0]);
		int M = Integer.parseInt(split[1]);
		char[][] map = new char[N][M];
		Point start = null;
		for(int i=0;i<N;i++) {
			split = br.readLine().split("");
			for(int j=0;j<M;j++) {
				map[i][j] = split[j].charAt(0);
				if(split[j].equals("I")) {
					start = new Point(i, j);
				}
			}
		}
		
		int count = 0;
		boolean[][] visit = new boolean[N][M];
		Queue<Point> queue = new ArrayDeque<>();
		queue.offer(start);
		
		while(!queue.isEmpty()) {
			Point now = queue.poll();
			int x = now.x;
			int y = now.y;
			for(int d=0;d<4;d++) {
				int X = x+dx[d];
				int Y = y+dy[d];
				
				if(X<0 || X>=N || Y<0 || Y>=M || map[X][Y] == 'X' || visit[X][Y]) {
					continue;
				}
				
				if(map[X][Y] == 'P') {
					count++;
				}
				
				queue.offer(new Point(X, Y));
				visit[X][Y] = true;
			}
		}
		
		
		if(count == 0) {
			System.out.println("TT");
		}
		else {
			System.out.println(count);
		}
	}
}