c c++ 언어 공부

백준 21736번 : 헌내기는 친구가 필요해 (C 언어)

Code C 2023. 6. 10. 00:48

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

 

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

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

www.acmicpc.net

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
 
int n, m;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
char arr[601][601] = { 0, };
int visit[601][601] = { 0, };
int count = 0;
 
void dfs(int x, int y)
{
    visit[x][y] = 1;
    for (int k = 0; k < 4; k++)
    {
        int x_ = x + dx[k];
        int y_ = y + dy[k];
        if (x_ >= 0 && x_ < n && y_ >= 0 && y_ < m && arr[x_][y_] != 'X'&&visit[x_][y_]==0)
        {
            if (arr[x_][y_] == 'P' && visit[x_][y_] == 0)
            {
                count++;
                visit[x_][y_] = 1;
            }
            dfs(x_, y_);
        }
    }
}
 
int main() {
    int i, j;
    int flag = 0;
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++)
    {
        scanf("%s", arr[i]);
    }
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
            if (arr[i][j] == 'I')
            {
                dfs(i, j);
                flag = 1;
                break;
            }
        }
        if (flag == 1)
        {
            break;
        }
    }
    if (count == 0)
    {
        printf("TT");
    }
    else
    {
        printf("%d", count);
    }
    return 0;
}
 cs

1. 문제 설명

이 문제는 2차원 맵에서 시작점('I')에서 목표지점('P')까지 찾아가는 문제입니다. 맵은 'I', 'P'와 함께 장애물을 표시하는 'X' 문자로 구성되어 있습니다. 장애물 'X'는 우리의 탐색을 방해하며, 'P'는 우리가 찾아야 하는 목표입니다.

2. 알고리즘

해당 문제를 풀기 위해 깊이 우선 탐색(DFS, Depth First Search) 알고리즘을 사용하였습니다. DFS는 시작점에서부터 가장 깊숙히 들어갈 수 있는 곳까지 탐색한 후, 다시 뒤로 돌아와서 다른 경로를 탐색하는 방식입니다. 이를 이용하여 'I'부터 시작해 'P'를 찾아나갑니다.

3. 코드 설명

  1. dx, dy 배열을 사용하여 현재 위치에서 상하좌우로 이동할 수 있는 위치를 나타냅니다.
  2. DFS 함수는 인자로 현재 위치 x, y를 받습니다. 방문한 곳은 visit 배열에 체크를 하고, 상하좌우로 이동 가능한 위치에 대해 방문하지 않았고, 그 위치가 장애물('X')이 아니라면, 그 위치가 목표('P')인지 확인하고, 목표라면 count를 증가시키고, 목표가 아니라면 다음 위치로 이동합니다.
  3. main 함수에서는 먼저 맵의 크기 n, m을 입력 받습니다. 그 다음에 맵의 정보를 입력받습니다. 맵 정보를 받은 후에는 'I'의 위치를 찾아 DFS를 시작합니다.
  4. 마지막으로 찾은 'P'의 개수를 출력합니다. 만약 'P'를 찾지 못했다면 'TT'를 출력합니다.