백준 21736번 문제 c++ 풀이#

문제#

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

도연이가 다니는 대학의 캠퍼스는 $N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 ($x$, $y$)에 있다면 이동할 수 있는 곳은 ($x+1$, $y$), ($x$, $y+1$), ($x-1$, $y$), ($x$, $y-1$)이다.
단, 캠퍼스의 밖으로 이동할 수는 없다.

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

입력#

첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 $N$ ( $1 \leq N \leq 600$ ),$M$ ($1 \leq M \leq 600$)이 주어진다.

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

출력#

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

예제 입력 1#

입력:
3 5
OOOPO
OIOOX
OOOXP

출력: 1

예제 입력 2#

입력:
3 3
IOX
OXP
XPP

출력:
TT

아이디어#

1. DFS를 이용해 순차적으로 퍼져나가면서 탐색한다.

1차 시도#

#include <iostream>

int N, M;

char* data;
char** arr;
bool visit[600][600];
int dx[4]{1, -1, 0, 0};
int dy[4]{0, 0, 1, -1};

int dfs(int x, int y)
{
    visit[y][x] = true;
    int visitPeople = arr[y][x] == 'P' ? 1 : 0;

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

        if (newX >= M || newX < 0 || newY >= N || newY < 0) continue;
        if (visit[newY][newX]) continue;
        if (arr[newY][newX] == 'X') continue;
        visitPeople += dfs(newX, newY);
    }

    return visitPeople;
}

int main()
{
    std::cin >> N >> M;

    int startX, startY;

    data = new char[N * M];
    arr = new char*[N];

    for (int i = 0; i < N; ++i)
    {
        arr[i] = data + (i * M);
        for (int j = 0; j < M; ++j)
        {
            arr[i][j] = data[i * M + j];
            char x;
            std::cin >> x;
            arr[i][j] = x;
            if (x == 'I')
            {
                startX = j;
                startY = i;
            }
        }
    }

    int result = dfs(startX, startY);

    if (result == 0)
        std::cout << "TT";
    else
        std::cout << result;

    delete[] data;
    delete[] arr;
}

결과

맞았습니다!!

깃헙 링크 : link