[ 백준 2424 ] 부산의 해적 (C++)
백준의 부산의해적(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<int, int> Start, End, HaeJuk; int dx[] = { 0, 0, 1, -1 }; int dy[] = { 1, -1, 0, 0 }; 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<int, int>> 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<int, int>, 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 |