헌내기는 친구가 필요해

문제

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

문제 설명

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다.

도연이가 다니는 대학의 캠퍼스는 NXM 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x, y)에 있다면 이동할 수 있는 곳은 (x+1, y), (x, y+1, (x-1, y), (x, y-1)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

제한 사항

첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 N, M(1≤N≤600, 1≤M≤600)이 주어진다.

둘째 줄부터 N개의 줄에는 캠퍼스의 정보들이 주어진다. O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.

첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다.

입출력 예

입력	출력
3 5
OOOPO
OIOOX
OOOXP	1
3 3
IOX
OXP
XPP	TT

아이디어

bfs 이제는 마스터!

제출 코드

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 two21763 {
    public static int nRow;
    public static int nCol;
    public static char[][] campus;
    public static boolean[][] visited;
    public static int[] dRow = {1, -1, 0, 0};
    public static int[] dCol = {0, 0, 1, -1};

    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer infoToken = new StringTokenizer(reader.readLine());
        nCol = Integer.parseInt(infoToken.nextToken());
        nRow = Integer.parseInt(infoToken.nextToken());
        campus = new char[nCol][nRow];
        visited = new boolean[nCol][nRow];

        int startCol = 0;
        int startRow = 0;

        for (int i = 0; i < nCol; i++) {
            String campusToken = reader.readLine();
            for (int j = 0; j < nRow; j++) {
                campus[i][j] = campusToken.charAt(j);
                if (campus[i][j] == 'I') {
                    startCol = i;
                    startRow = j;
                }
            }
        }

        int meeting = 0;

        Queue<int[]> toVisit = new LinkedList<>();
        toVisit.offer(new int[] {startCol, startRow});
        visited[startCol][startRow] = true;

        while(!toVisit.isEmpty()) {
            int[] now = toVisit.poll();

            for (int i = 0; i < 4; i++) {
                int nextCol = now[0] + dCol[i];
                int nextRow = now[1] + dRow[i];

                if (nextCol < 0 || nextCol >= nCol || nextRow < 0 || nextRow >= nRow) continue;
                if (visited[nextCol][nextRow]) continue;
                if (campus[nextCol][nextRow] == 'X') continue;

                if (campus[nextCol][nextRow] == 'P') meeting++;
                toVisit.offer(new int[] {nextCol, nextRow});
                visited[nextCol][nextRow] = true;
            }
        }

        if (meeting == 0) {
            System.out.println("TT");
        } else {
            System.out.println(meeting);
        }
    }

    public static void main(String[] args) throws IOException {
        new two21763().solution();
    }
}