[Java] baekjoon_21736 : 헌내기는 친구가 필요해

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

헌내기는 친구가 필요해 : Silver2

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

풀이

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int[] dx = { 1, -1, 0, 0 };
    private static int[] dy = { 0, 0, 1, -1 };

    public static void main(String[] args) throws Exception {
        
        // 도연 위치 (x, y)
        // 이동 가능 (x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)
        // O:빈공간, X:벽, I:도연, P:사람
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        char[][] campus = new char[N][M];
        int startX = -1, startY = -1;
        int peopleCnt = 0;

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                campus[i][j] = line.charAt(j);
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (campus[i][j] == 'I') {
                    startX = i;
                    startY = j;
                }
            }
        }

        peopleCnt = bfs(campus, N, M, startX, startY);
        bw.write(peopleCnt == 0 ? "TT\n" : peopleCnt + "\n");
        bw.flush();
        br.close();
        bw.close();
    }

    private static int bfs(char[][] campus, int N, int M, int startX, int startY) {
        boolean[][] visited = new boolean[N][M];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{ startX, startY });
        visited[startX][startY] = true;
        int peopleCnt = 0;
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny] && campus[nx][ny] != 'X') {
                    visited[nx][ny] = true;
                    queue.add(new int[]{ nx, ny });
                    if (campus[nx][ny] == 'P') {
                        peopleCnt++;
                    }
                }
            }
        }
        return peopleCnt;
    }
}

 

이 문제는 BFS를 이용했다.

 

도연의 시작 위치 찾기

• campus 배열을 순회하면서 도연의 시작 위치 I를 찾는다
• 도연의 시작 위치를 startX와 startY 변수에 저장한다.

BFS 알고리즘을 사용하여 탐색

• bfs 메서드는 도연의 시작 위치를 기준으로 BFS를 수행한다.
• visited 배열을 사용하여 방문한 위치를 기록한다.
• Queue를 사용하여 BFS를 구현한다.
• 상하좌우 이동을 위해 dx와 dy 배열을 사용한다.
• 큐에서 위치를 꺼내 상하좌우로 이동 가능한 모든 위치를 탐색하고, 사람인 P를 발견하면 peopleCnt를 증가시킨다.

결과 출력

• 탐색이 끝난 후, 만약 peopleCnt가 0이면 "TT"를 출력하고, 그렇지 않으면 peopleCnt 값을 출력합니다.