백준 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

아이디어#

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

1차 시도#

1
#include <iostream>
2

3
int N, M;
4

5
char* data;
6
char** arr;
7
bool visit[600][600];
8
int dx[4]{1, -1, 0, 0};
9
int dy[4]{0, 0, 1, -1};
10

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

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

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

27
    return visitPeople;
28
}
29

30
int main()
31
{
32
    std::cin >> N >> M;
33

34
    int startX, startY;
35

36
    data = new char[N * M];
37
    arr = new char*[N];
38

39
    for (int i = 0; i < N; ++i)
40
    {
41
        arr[i] = data + (i * M);
42
        for (int j = 0; j < M; ++j)
43
        {
44
            arr[i][j] = data[i * M + j];
45
            char x;
46
            std::cin >> x;
47
            arr[i][j] = x;
48
            if (x == 'I')
49
            {
50
                startX = j;
51
                startY = i;
52
            }
53
        }
54
    }
55

56
    int result = dfs(startX, startY);
57

58
    if (result == 0)
59
        std::cout << "TT";
60
    else
61
        std::cout << result;
62

63
    delete[] data;
64
    delete[] arr;
65
}