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

문제

입력

출력

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

문제 풀이

• 해당 문제는 너비 우선 탐색으로 풀이를 진행한다
• 자세한 설명은 코드의 주석으로 설명

코드

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 601;
int M, N; // 가로 세로
bool visit[MAX][MAX]; // 방문여부
char input[MAX][MAX]; // 입력받는 문자 확인 
int dy[] = { 1,-1,0,0 };
int dx[] = { 0,0,1,-1 };
int ans; // 만날 수 있는 사람의 숫자
queue<pair<int, int>> q;

void BFS() {
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

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

            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if (visit[nx][ny] == 0) { // 방문하지 않았을 경우
                    visit[nx][ny] = true; // 방문한 것으로 체크
                    if (input[nx][ny] == 'P') { // 사람을 만났을 경우 
                        ans++; // ans 증가
                    }
                    q.push({ nx,ny }); // 큐에 삽입하여 재귀
                }
            }

        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();

    cin >> N >> M; // 가로와 세로 줄 입력

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> input[i][j];
            if (input[i][j] == 'I') { // 처음 도연이가 시작한 지점
                visit[i][j] = true; // 방문 여부 확인 후
                q.push({ i,j }); // 큐에 삽입
            }
            else if (input[i][j] == 'X') {
                visit[i][j] = true;  // 벽의 경우 방문여부를 true 만들어 지나가지 못하게 만듬
            }
        }
    }
    BFS(); // 너비 우선 탐색
    if (ans != 0) { // 한 명이라도 만났을 경우
        cout << ans; // 정답 출력
    }
    else // 못 만났을 경우
        cout << "TT"; // TT 출력

    return 0;
}