제9회 대학생 프로그래밍 경시대회 문제 E Maze

ProgrammingAlgorithm
Algorithm, C++, ICPC, Programming

소스코드

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <iostream>
#include <cmath>
using namespace std;
char** maze;    // 미로
int** usedEnergyMaze;    // 에너지 사용량
int M, N;    // 행, 열
// 재귀적으로 미로 전 영역의 에너지 사용량을 기록한다.
void GetUsedEnergy(int row, int col, int energy)
{
    // 미로 밖으로 벗어난 경우
    if(row < 0 || col < 0 || row >= M || col >= N)
    {
        return;
    }
    // 벽을 만나면 에너지 사용량을 증가시킨다.
    if(maze[row][col] == '*')
    {
        energy++;
    }
    // 알려진 에너지 사용량보다 적으면 갱신한다.
    if(energy < usedEnergyMaze[row][col])
    {
        usedEnergyMaze[row][col] = energy;
    }
    else
    {
        return;
    }
    // 네 방향으로 반복해서 탐색한다.
    GetUsedEnergy(row - 1, col, energy);
    GetUsedEnergy(row + 1, col, energy);
    GetUsedEnergy(row, col - 1, energy);
    GetUsedEnergy(row, col + 1, energy);
}
// 해당 에너지량으로 로봇을 구출할 수 있을지 판단한다.
bool canRescue(int energy)
{
    // 출발 위치를 구한다.
    int row, col;
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(maze[i][j] == 'S')
            {
                row = i;
                col = j;
            }
        }
    }
    // 미로 전 영역의 에너지 사용량을 구한다.
    GetUsedEnergy(row, col, 0);
    // 도착 위치까지의 에너지 사용량이 로봇의 에너지보다 작은지 판단한다.
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(maze[i][j] == 'T')
            {
                if(usedEnergyMaze[i][j] <= energy)
                {
                    return true;
                }
            }
        }
    }
    return false;
}
int main()
{
    int T;    // 테스트 케이스의 개수
    cin >> T;
    for(int i = 0; i < T; i++)
    {
        int k;    // 로봇의 충전된 에너지
        cin >> k;
        cin >> M >> N;
        // 미로를 초기화한다.
        maze = new char*[M];
        for(int j = 0; j < M; j++)
        {
            maze[j] = new char[N];
        }
        for(int j = 0; j < M; j++)
        {
            for(int k = 0; k < N; k++)
            {
                cin >> maze[j][k];
            }
        }
        // 에너지 사용량을 초기화한다.
        usedEnergyMaze = new int*[M];
        for(int j = 0; j < M; j++)
        {
            usedEnergyMaze[j] = new int[N];
        }
        int intMax = pow(2, 31) - 1;    // 정수의 최대값
        for(int j = 0; j < M; j++)
        {
            for(int k = 0; k < N; k++)
            {
                usedEnergyMaze[j][k] = intMax;
            }
        }
        // 로봇을 구하면 y를 구하고, 아니면 n을 구한다
        if(canRescue(k))
        {
            cout << 'y' << endl;
        }
        else
        {
            cout << 'n' << endl;
        }
        // 메모리를 해제한다.
        for(int j = 0; j < M; j++)
        {
            delete[] usedEnergyMaze[j];
        }
        delete[] usedEnergyMaze;
        for(int j = 0; j < M; j++)
        {
            delete[] maze[j];
        }
        delete[] maze;
    }
    return 0;
}

주절주절

재귀적인 탐색 문제이다. 4방향으로 탐색하며 각 셀마다 이동하는데 사용되는 최소 에너지량을 구한다. 이미 방문한 셀이라도 더 적은 에너지로 갈 수 있으면 이동해야 한다.

Share Comments