[Java] BOJ 21736 헌내기는 친구가 필요해

문제 

문제 링크 https://www.acmicpc.net/problem/21736

• 도연이가 다니는 대학의 캠퍼스는 N×M크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다.
• 예를 들어, 도연이가 (x, y)에 있다면 이동할 수 있는 곳은 (x+1, y), (x, y+1), (x−1, y), (x, y−1)이다.
• 단, 캠퍼스의 밖으로 이동할 수는 없다.
• 불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.
• 첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 N(1 ≤ N ≤ 600), M(1 ≤ M ≤ 600)이 주어진다.
• 둘째 줄부터 N개의 줄에는 캠퍼스의 정보들이 주어진다. 
• O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.
• 첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다.

아이디어

• I의 좌표값을 기준으로 BFS를 돌리면서 상하좌우 좌표를 탐색하고 O일 경우, Queue에 좌표값을 넣어서 계속 탐색한다.
• 좌표값이 P일 경우, 사람 수를 카운트 해주고 마찬가지로 Queue에 좌표값을 넣어 계속 탐색한다.

겪은 시행착오

• X

BFS는 얼추 이제 이해한 것 같다..! (DFS가 문제네....)

코드

import java.awt.*;
import java.io.*;
import java.util.*;

public class BOJ21736 {

    static int N;
    static int M;
    static char campus[][];
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static boolean visited[][];
    static int cnt;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 행
        N = Integer.parseInt(st.nextToken());
        // 열
        M = Integer.parseInt(st.nextToken());

        // 캠퍼스를 저장할 2차원 배열
        campus = new char[N][M];
        // 배열의 방문 여부
        visited = new boolean[N][M];
        // 만난 사람의 수
        cnt = 0;

        // 도연의 좌표를 저장할 변수
        int d_x = 0;
        int d_y = 0;

        for(int i = 0; i < N; i++){
            String s = br.readLine();

            for(int j = 0; j < M; j++){
                char c = s.charAt(j);

                // c가 I일 경우, 그 좌표가 도연의 좌표이므로
                // 도연의 좌표를 변수에 저장
                if(c == 'I'){
                    d_x = i;
                    d_y = j;
                }

                // 캠퍼스에 정보를 저장
                campus[i][j] = c;
            }
        }

        // 도연이의 좌표료 BFS를 돌림
        BFS(d_x, d_y);

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

    public static void BFS(int x, int y){
        Queue<Point> q = new LinkedList<>();

        // 도연이가 있는 좌표를 Queue에 넣어줌
        q.offer(new Point(x, y));

        // 해당 좌표를 방문처리
        visited[x][y] = true;

        // Queue가 빌때까지 반복
        while(!q.isEmpty()){
            // 좌표값을 변수에 저장
            int node_x = q.peek().x;
            int node_y = q.peek().y;

            q.poll();

            for(int i = 0; i < 4; i++){
                // 상하좌우의 좌표값을 저장
                int nx = node_x + dx[i];
                int ny = node_y + dy[i];

                // 만약 해당 좌표값이 배열범위를 넘어간다면 continue
                if(nx >= N || nx < 0 || ny >= M || ny < 0){
                    continue;
                }

                // 범위안에 들고 해당 노드를 방문하지 않았다면
                if(!visited[nx][ny]){
                    // 해당 노드를 방문처리하고
                    visited[nx][ny] = true;

                    // 만약 해당 배열값이 P라면 사람이 있다는 뜻이므로
                    if(campus[nx][ny] == 'P'){
                        // 사람 수 + 1 하고
                        cnt = cnt + 1;

                        // Queue에 해당 좌표값을 넣음
                        q.offer(new Point(nx, ny));
                    }
                    // 배열값이 O라면 빈 공간이므로
                    else if(campus[nx][ny] == 'O'){
                        // Queue에 해당 좌표값을 넣음
                        q.offer(new Point(nx, ny));
                    }
                }
            }
        }

    }
}