[ BOJ Code ]/# BOJ -

[ 백준 2424 ] 부산의 해적 (C++)

얍문 2020. 2. 29. 01:32

백준의 부산의해적(2424) 문제이다.

[ 문제 바로가기 ]


[ 문제풀이 ]

1) 본인은 가장 먼저 해적에 대한 맵을 만들어 주었다. 해적은 수아의 움직임에 따라서 움직일수도 있고, 안움직일 수도 있지만

   해적이 가장 빠르게 움직일 수 있는 값은 정해져있다.

   다음과 같은 상황을 예시로 알아보자.

  

   이런 경우에 위에서 표시된 빨간색점에 해적은 몇초에 갈 수 있을까 ??

   2초에 갈수도 있고, 중간에 움직이지 않는 경우를 생각해보면 3초에 갈수도, 4초에 갈수도, 5초에 갈수도 있다

   그렇다면 수아가 2초에 파란점을 갈 수 있을까 ? 3초에 파란점을 갈 수 있을까 ?

   수아는 저 파란점에 갈 수가 없다. 해적이 빨간점에 3초에 올 수도, 4초에 올 수도, 5초에 올 수도 있지만 가장 빠르게 온다면

   2초에 올 수도 있기 때문에, 2초에 해적과 일직선상에 있어서 수아는 죽게 된다.

   즉, 해적이 특정 좌표와 몇 초에 일직선 상에 존재하는지를 저장하는 맵을 만들어 주었다.

   말이 조금 이상한데 쉽게 생각하면 다음과 같다.

  

   해적이 위와 같이 위치하게 된다면, 결과적으로 수아는 해적과 같은 좌표에 있어야 죽는 것이 아닌, 같은 행 혹은

   같은 열에만 있어도(중간에 섬이 없다고 가정하면) 죽기 때문에 해적이 해당 좌표를 최소시간 몇 초에 바라볼 수 있는지

   맵을 작성한다는 것이다. 즉, 위의 그림과 같은 경우에는 다음과 같이 맵이 그려질 것이다.

   

   즉, 위의 값들은 "해당 좌표에 도달하는 최단시간"을 나타낸 것이 아닌, "해적이 최소시간에 바라볼 수 있는 시간"(?)을

   나타낸 것이다. 말로 표현하려니 조금 이상하다..

  

2) 해적의 맵을 만드는 과정에 대해서 알아보자.

   가장 먼저, 너비 우선 탐색(BFS)로 해적이 각 좌표에 갈 수 있는 최소 시간을 구해보았다.

  

   이 맵을 예시로 알아보자. 가장 먼저, 해적이 각 좌표에 갈 수 있는 최소 시간을 구해서 값을 넣어준다면 다음과 같이

   표가 채워질 것이다.

  

   그럼 이 맵을 토대로, 각 행과 각 열에서 최소값을 찾아서 설정해 주는 것이다.

   하지만, 이 맵에서 그대로 갱신을 하게 되면, 그 다음에 진행되는 행, 혹은 그 다음에 진행될 열의 값들에 지장이

   생기므로, 위의 값들을 저장할 맵을 하나 만들고, 해적의 움직임을 저장할 또 하나의 맵을 선언해서 저장해 주어야 한다.

   먼저 0행부터 봐보도록 하자. 값을 설정해줄 초기 최소값은 무한대로 초기화를 시켜놓는다.

   (지금부터 이 값을 'Min' 값이라고 하겠음.)

   1. (0, 0)의 값과 Min 값을 비교한다. 0 < 무한대 이므로 (0, 0)의 값은 0으로 설정. 동시에 Min 값을 0으로 설정.

   2. (0, 1)의 값과 Min 값을 비교한다. 1 > 0 이므로, (0, 1)의 값은 0으로 설정.

   3. 2번에 의한 계산과 마찬가지로 (0, 2) ~ (0, 5) 까지 모두 '0'으로 설정됨.

   여기까지 하면, 하나의 행에 대한 계산이 완료된 것이 아니다. 역순으로도 한번 체크를 해주어야 한다.

   왜 그럴까 ?? 해적의 위치를 아래 그림과 같이 반대 위치라고 생각해보자.

  

   이 경우에, 해적위치에서 BFS탐색을 돌려서, 각 좌표마다 갈 수 있는 최단거리를 설정해주면 다음과 같이 될 것이다.

  

   그리고 위에서 말한 1 ~ 3번 과정을 그대로 다시한번 해보자.

   1. (0, 0)의 값과 Min 값을 비교한다. 5 < 무한대 이므로 (0, 0)의 값은 5으로 설정. 동시에 Min 값을 5로 설정.

   2. (0, 1)의 값과 Min 값을 비교한다. 4 < 5 이므로, (0, 1)의 값은 4로 설정.

   3. 2번에 의한 계산과 마찬가지로 (0, 2) ~ (0, 5) 까지 순차적으로 '3', '2', '1', '0' 이 설정됨.

   뭔가 계산이 이상하다. 분명히, 0행은 0초로 값이 설정되어야 맞지만, 위와 같은 경우 제대로 설정되지가 않는다.

   따라서, 역순으로도 한번 해주는 것이다. 위의 과정을 !

   1. (0, 5)의 값과 Min 값을 비교한다. 0 < 무한대 이므로 (0, 5)의 값은 0으로 설정. 동시에 Min값을 0으로 설정.

   2. (0, 4)의 값과 Min 값을 비교한다. 1 > 0 이므로 (0, 4)의 값은 0으로 설정.

   3. 2번에 의한 계산과 마찬가지로 (0, 3) ~ (0, 0) 은 모두 '0'으로 설정.

   이렇게 계산을 정순으로 한번, 역순으로 한번 해주어야 한다.

   또한, 방금 위에서 설명한 부분에는 중간에 섬이 없는데, 섬이 있는 경우에는 Min값을 다시 무한대로 설정해 주어야 한다.

   왜냐하면, 그 전의 최소값에 그 다음 좌표가 영향을 미치지 않기 때문에 섬이 있을 경우에는 최소값으로 저장해 주어야 한다.

  

   열을 설정하는 과정도 행과 굉장히 비슷한데, 한가지를 더 유의해 주어야 한다.

   이미, 위에서 한 '행에 대한 계산' 때문에 해적맵이 어느정도는 값이 설정되어 있는 상태일 것이다.

   이 값들을 다시 열에 대한 값들을 비교해서 맵을 채워 넣어야 하기 때문에, 기존에 설정되어 있는 값들과 지금부터 할

   열에 대한 값들을 비교해서 더 작은 값으로 설정을 해주면 된다.

  

3) 이런식으로 해적의 맵을 모두 만들었다면, 이제 수아를 움직여 주기만 하면 된다.

   이 부분 또한, 본인은 너비우선탐색(BFS)으로 구현해 주었고, 탐색 조건은, 만들어 놓은 해적맵과 비교를 하면서

   "현재 좌표에 수아가 도달했을 때 걸리는 시간이, 해적이 가장 빠르게 움직였을 때, 해당 좌표를 바라볼 수 있는 시간 보다

    더 빠르다면" 탐색을 진행해 주었다.

  

[ 소스코드 ]

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 700
#define INF 987654321
using namespace std;
 
int N, M;
char MAP[MAX][MAX];
int H_MAP[MAX][MAX];
int HC_MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
pair<intint> Start, End, HaeJuk;
 
int dx[] = { 001-1 };
int dy[] = { 1-100 };
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'Y'
            {
                Start.first = i;
                Start.second = j;
                MAP[i][j] = '.';
            }
            else if (MAP[i][j] == 'T')
            {
                End.first = i;
                End.second = j;
                MAP[i][j] = '.';
            }
            else if (MAP[i][j] == 'V')
            {
                HaeJuk.first = i;
                HaeJuk.second = j;
                MAP[i][j] = '.';
            }
            HC_MAP[i][j] = INF;
        }
    }
}
 
void Arrange_MAP()
{
    for (int i = 0; i < N; i++)
    {
        int MinValue = INF;
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == 'I')
            {
                MinValue = INF;
                H_MAP[i][j] = INF;
                continue;
            }
            MinValue = Min(MinValue, HC_MAP[i][j]);
            H_MAP[i][j] = MinValue;
        }
 
        MinValue = INF;
        for (int j = M - 1; j >= 0; j--)
        {
            if (MAP[i][j] == 'I')
            {
                MinValue = INF;
                H_MAP[i][j] = INF;
                continue;
            }
            MinValue = Min(MinValue, HC_MAP[i][j]);
            H_MAP[i][j] = Min(MinValue, H_MAP[i][j]);
        }
    }
 
    for (int j = 0; j < M; j++)
    {
        int    MinValue = INF;
        for (int i = 0; i < N; i++)
        {
            if (MAP[i][j] == 'I'
            {
                MinValue = INF;
                H_MAP[i][j] = INF;
                continue;
            }
            MinValue = Min(MinValue, HC_MAP[i][j]);
            H_MAP[i][j] = Min(MinValue, H_MAP[i][j]);
        }
        
        MinValue = INF;
        for (int i = N - 1; i >= 0; i--)
        {
            if (MAP[i][j] == 'I')
            {
                MinValue = INF;
                H_MAP[i][j] = INF;
                continue;
            }
            MinValue = Min(MinValue, HC_MAP[i][j]);
            H_MAP[i][j] = Min(MinValue, H_MAP[i][j]);
 
        }
    }
}
 
void Make_HaeJuk_Map()
{
    queue<pair<intint>> Q;
    Q.push(make_pair(HaeJuk.first, HaeJuk.second));
    HC_MAP[HaeJuk.first][HaeJuk.second] = 0;
    int Level = 0;
 
    while (Q.empty() == 0)
    {
        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 && ny >= 0 && nx < N && ny < M)
            {
                if (MAP[nx][ny] == '.' && HC_MAP[nx][ny] > HC_MAP[x][y] + 1)
                {
                    HC_MAP[nx][ny] = HC_MAP[x][y] + 1;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
    Arrange_MAP();
}
 
void Move_SooA()
{
    queue<pair<pair<intint>int>> Q;
    Q.push(make_pair(make_pair(Start.first, Start.second), 0));
    Visit[Start.first][Start.second] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (x == End.first && y == End.second)
        {
            cout << "YES" << endl;
            return;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (MAP[nx][ny] == '.' && Visit[nx][ny] == false)
                {
                    if (H_MAP[nx][ny] > Cnt + 1)
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                    }
                }
            }
        }
    }
    cout << "NO" << endl;
}
 
void Solution()
{
    Make_HaeJuk_Map();
    Move_SooA();
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}
cs