[CLASS 3: BFS] 백준 21736 헌내기는 친구가 필요해

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

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

 

# 코드

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

public class Main {
    static int n, m;
    static int arr[][]; // 캠퍼스의 정보를 저장하는 2차원 배열
    static boolean visited[][]; // 방문 여부를 기록하는 2차원 배열
    static point doyeon_pos;  // 도연이의 초기 위치를 저장하는 객체
    static int d_row[] = { -1, 0, 1, 0 }; // 상하좌우 이동을 위한 행 변화량
    static int d_col[] = { 0, -1, 0, 1 }; // 상하좌우 이동을 위한 열 변화량
    static int person_cnt = 0; // 만난 사람의 수를 저장하는 변수

    // 점(좌표)을 나타내는 클래스
    static class point {
        int x; // 행
        int y; // 열

        public point(int x, int y) { // 생성자: 좌표 초기화
            this.x = x;
            this.y = y;
        }
    }

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

        // 첫 번째 줄: 캠퍼스 크기 입력
        String input[] = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        // 배열 초기화
        arr = new int[n][m];
        visited = new boolean[n][m];

        // 캠퍼스 정보 입력
        for (int i = 0; i < n; i++) {
            String info = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = info.charAt(j); // 문자를 캠퍼스 정보에 저장 (ASCII 값이 저장됨)

                // 도연이 위치 ('I') 저장
                if (arr[i][j] == 'I')
                    doyeon_pos = new point(i, j); // 도연이의 초기 좌표
            }
        }

        // BFS(너비 우선 탐색)를 위한 큐 초기화
        Queue<point> q = new LinkedList<>();
        q.add(doyeon_pos); // 도연이의 초기 위치를 큐에 추가
        visited[doyeon_pos.x][doyeon_pos.y] = true; // 초기 위치 방문 처리

        // BFS 탐색 시작
        while (!q.isEmpty()) {
            point cur_pos = q.poll(); // 현재 위치를 큐에서 꺼냄

            // 현재 위치에 사람이 있으면 cnt++
            if (arr[cur_pos.x][cur_pos.y] == 'P') {
                person_cnt++;
            }

            // 상하좌우 탐색
            // d_row, d_col 변화량은 다음과 같음
            // [i = 0 일때] -1, 0 상(위로 이동)
            // [i = 1 일때] 0, -1 좌(왼쪽 이동)
            // [i = 2 일때] 1, 0 하(아래로 이동)
            // [i = 3 일때] 0, 1 우(오른쪽 이동)
            for (int i = 0; i < 4; i++) {
                int next_x = cur_pos.x + d_row[i]; // 다음 행 위치
                int next_y = cur_pos.y + d_col[i]; // 다음 열 위치

                // 1. 캠퍼스 범위를 벗어나거나 이미 방문했으면 무시
                if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= m || visited[next_x][next_y] == true) {
                    continue;
                }
                // 2. 벽('X')이면 무시
                if (arr[next_x][next_y] == 'X') {
                    continue;
                }
                // 3. 방문 가능한 위치를 큐에 추가하고 방문 처리
                q.add(new point(next_x, next_y));
                visited[next_x][next_y] = true;
            }
        }

        if (person_cnt == 0) {
            System.out.println("TT");
        } else {
            System.out.println(person_cnt);
        }
        br.close();
    }
}

• 도연이(I)가 캠퍼스에서 만난 사람(P)의 수를 계산하는 문제이다.
• 캠퍼스 크기 (n, m)과 캠퍼스 정보(2차원 배열 arr)를 입력받고, 동시에  캠퍼스에서 도연이의 초기 위치('I')를 찾아 저장한다.
• BFS 탐색을 위해 도연이의 초기 위치를 큐에 넣고 방문 처리한다.
• 상하좌우 이동은 d_row와 d_col 배열을 이용한다.
  • d_row: 행 방향 이동 변화량
  • d_col: 열 방향 이동 변화량
• 큐에서 현재 위치를 꺼내 상하좌우를 확인하며 탐색을 진행한다. (BFS 탐색 진행)
• 조건:
  1. 범위를 벗어나거나 이미 방문한 위치는 무시.
  2. 벽('X')인 경우 무시.
  3. 사람이 있는 위치('P')를 발견하면 person_cnt를 증가.

 

 

Q. 위 코드에서 arr 배열은 int 타입으로 선언되어 있는데, arr[i][j] = info.charAt(j);처럼 char 문자를 저장하는 것이 가능할까?

A. 가능하다.

Java에서 char 타입이 int로 암시적으로 변환되기 때문이다.

 

char는 내부적으로 ASCII 값을 가지며, 숫자 형태로 int 배열에 저장된다.

예를 들어, 'I'는 ASCII 값인 73으로 저장되며, 비교문에서 if (arr[i][j] == 'I')처럼 사용해도 문제없이 작동한다.

 

하지만, 배열이 문자 데이터를 저장하기 위한 목적이라면 arr를 char[][] 타입으로 선언하는 것이 더 명확하기는 하다.

(데이터가 ASCII 값이 아닌 문자 그대로 저장되어 코드의 가독성이 높아지기 때문이다.)

 

 

 

코드는 아래 블로그를 참고했다.

[백준] 21736번 : 헌내기는 친구가 필요해 (JAVA)