[백준 / Java] 21736: 헌내기는 친구가 필요해 (BFS)

난이도: Silver 2

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

 

문제

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

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

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

입력

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

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

출력

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

---

 

2차원 배열을 활용한 BFS 문제의 가장 기본 문제이다.

 

상, 하, 좌, 우를 탐색할 수 있는 배열을 다음과 같이 먼저 생성해 두자.

이 배열은 정말 많이 사용되므로 아예 외워두자.

static int[] dx = {-1, 0, 1, 0}; // 상, 하 이동

static int[] dy = {0, -1, 0, 1}; // 좌, 우 이동

 

BFS를 수행할 때 현재 좌표를 기준으로 상, 하, 좌, 우를 모두 탐색하면 된다.

현재 x좌표와 y좌표는 큐에 삽입했던 것을 뽑아내면 된다.

참고로 큐에 삽입할 때에는 int[] 배열로 한 번에 삽입한다.

 

int[] now = queue.poll();   // 현재 칸

 

// 현재 칸의 상, 하, 좌, 우를 모두 탐색

for (int i = 0; i < 4; i++)

    int x = now[0] + dx[i];    // 인접한 x좌표

    int y = now[1] + dy[i];    // 인접한 y좌표

 

인접한 좌표(x, y)가 유효한 인덱스 범위를 벗어나는지 체크하고, => if (x < 0 || y < 0 || x >= N || y >= M)

visited[x][y]를 이미 방문했는지 체크하고, => if (visited[x][y])

문제에 주어진 2차원 배열의 [x][y]값이 벽인지 체크하자. => if (campus[x][y] == 'X')

위와 같은 조건에 속하면 그 칸에 갈 수가 없으므로 모두 건너뛴다.

 

그 다음에는 큐에 삽입하고, 방문 체크를 하고, 해당 칸에 친구가 있다면 count를 1 증가시키면 된다.

 

위 과정을 큐가 빌 때까지 반복한다.

 

 

주석에 설명을 한 줄 한 줄 자세히 적어 놓았다.

자, 이제 코드를 보자.

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 P21736_헌내기는친구가필요해 {
    static int N, M;                    // 캠퍼스의 세로, 가로 크기
    static int[] dx = {-1, 0, 1, 0};    // 상, 하 이동
    static int[] dy = {0, -1, 0, 1};    // 좌, 우 이동
    static char[][] campus;                // 2차원 캠퍼스 배열
    static boolean[][] visited;            // 2차원 방문 체크 배열                
    
    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());    
        campus = new char[N][M];                    
        visited = new boolean[N][M];                
        int x = -1, y = -1;        // 도연이의 현재 위치
        
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                campus[i][j] = line.charAt(j);
                if (campus[i][j] == 'I') {    // 해당 좌표에 있는 글자가 도연이에 해당한다면
                    x = i;    // 도연이의 x좌표 위치 저장
                    y = j;    // 도연이의 y좌표 위치 저장
                }
            }
        }
        
        int count = bfs(x, y);        // 도연이가 만날 수 있는 사람의 수
        
        if (count != 0) {    // 도연이가 사람을 만날 수 있는 경우
            System.out.println(count);    // 도연이가 만날 수 있는 사람의 수 출력
        } else {    // 도연이가 아무도 만나지 못한 경우
            System.out.println("TT");    
        }
    }
    
    public static int bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();    // bfs 수행을 위한 큐
        queue.add(new int[] {x, y});    // 큐에 도연이의 위치를 삽입
        visited[x][y] = true;            // 도연이의 위치를 방문 체크
        int count = 0;                    // 도연이가 만날 수 있는 사람의 수
        
        while (!queue.isEmpty()) {
            int[] now = queue.poll();    // 큐에서 현재 좌표 뽑기
            
            // 현재 위치 기준으로 상하좌우 탐색
            for (int i = 0; i < 4; i++) {
                int nx = now[0] + dx[i];    // 인접한 x좌표
                int ny = now[1] + dy[i];    // 인접한 y좌표
                
                // 인접한 좌표 인덱스가 유효 범위에 속하지 않는다면 건너뛰기
                if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
                    continue;
                }
                
                // 인접 좌표를 이미 방문했거나, 벽이라면 건너뛰기
                if (visited[nx][ny] || campus[nx][ny] == 'X') {
                    continue;
                }
                
                queue.add(new int[] {nx, ny});    // 큐에 인접 좌표를 삽입
                visited[nx][ny] = true;            // 인접 좌표를 방문 체크
                
                if (campus[nx][ny] == 'P') {    // 인접 위치에 사람이 있다면
                    count++;    // 도연이가 만날 수 있는 사람의 수 1 증가
                }
            }
        }
        
        return count;    // 도연이가 만날 수 있는 사람의 수 리턴
    }
}