๋์ด๋ | ์ ๋ต๋ฅ |
โ โ โ โ | -% |
ํ๋ฆฌ๋ฏธ์ ์๊ณ ๋ฆฌ์ฆ ์ํด๋ฆฌ ๋นํ์๊ณ ์์ฆ3 4์ฃผ์ฐจ
๋ฌธ์
ํด๊ฒฐ
key point, ๋ฐฉ๋ฌธํ ์๊ฐ์ด ์์ ๊ณณ์ ์ฐ์ ์ ์ผ๋ก ๋ฐฉ๋ฌธํ๋ค. priority_queue
- ์ฐ์ ์์ ํ์ ๋ฐฉ๋ฌธํ ์๊ฐ๊ณผ ์ขํ๋ฅผ ์ ์ฅํ๋ค. → {time, {x, y}}
- ํ์ฌ ๋ณด๊ณ ์๋ ์์น์ ์ธ์ ํ ๊ณณ์ ํ์ธํ๋ฉด์
- ๋ฒฝ์ด ์๋ค๋ฉด ์๊ฐ์ ๊ทธ๋๋ก, ์ขํ๋ง ๋ค์ ์์น์ ๋ง์ถฐ ๋ฃ์ด์ค๋ค.
- ๋ฒฝ์ด ์๋ค๋ฉด ์๊ฐ์ +1, ๋ค์ ์์น ์ขํ๋ฅผ ๋ฃ์ด์ค๋ค.
- ์ด๋ ๊ฒ ์์ฐจ์ ์ผ๋ก ์ํํ๋ค๋ณด๋ฉด N,N ์์น์ ๋๋ฌํ๊ฒ ๋๊ณ ๊ทธ ๋์ time์ ์ถ๋ ฅํ๋ฉด ์ต์ ์๊ฐ์ด ๋๋ค.
์ฝ๋
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
|
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> p;
int n, ans = 1e9;
int dx[] = { 0,1,0, -1 }, dy[] = { 1,0,-1, 0 };
int arr[1005][1005], chk[1005][1005];
priority_queue<pair<int, p>, vector<pair<int, p>>, greater<pair<int, p>>> pq;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &arr[i][j]);
}
}
chk[0][0] = 1;
pq.push({ 1, {0,0} });
while (!pq.empty()) {
pair<int, p> front = pq.top();
pq.pop();
int time = front.first, x = front.second.first, y = front.second.second;
if (x == n - 1 && y == n - 1) {
printf("%d", time - 1);
break;
}
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= n || ny >= n || chk[nx][ny]) continue;
if (arr[nx][ny]) {
chk[nx][ny] = time;
pq.push({ time, { nx, ny } });
}
else {
chk[nx][ny] = time + 1;
pq.push({ time + 1, { nx, ny } });
}
}
}
return 0;
}
|
cs |
deque์ฌ์ฉ
์ด์ ์ ๋ฑ์ ์ ํ ์ฌ์ฉํด๋ณธ ์ ์ด ์์ด์ ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํด์ ๋ฌธ์ ๋ฅผ ํ์๋๊ฑด๋ฐ, ํด์ค์ ํ์ธํด๋ณด๋ ๋ฑ์ ์ฌ์ฉํ๊ณ ์์ด์ ์ ๋ ๋ฑ์ ์ด์ฉํด์ ๋ค์ ํ์ด๋ดค์ต๋๋ค.
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
|
#include <iostream>
#include<deque>
using namespace std;
typedef pair<int, int> p;
int arr[1005][1005], chk[1005][1005];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0};
deque<p> dq;
int main() {
int n; scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &arr[i][j]);
dq.push_back({ 0, 0 });
chk[0][0] = 1;
while (dq.size()) {
auto cur = dq.front();
int x = cur.first, y = cur.second;
dq.pop_front();
if (x == n - 1 && y == n - 1) {
printf("%d", chk[x][y] - 1);
return 0;
}
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= n || chk[nx][ny]) continue;
if (arr[nx][ny]) { //๋ค์ ๋ฐฉ๋ฌธํด์ผ ํ ๊ณณ์ด ๋ฒฝ์ด๋ผ๋ฉด ๋ฑ์ ์์ ์ ์ ์ ๋ฃ์ด์ค
chk[nx][ny] = chk[x][y];
dq.push_front({ nx, ny });
}
else { //๋ค์ ๋ฐฉ๋ฌธํด์ผ ํ ๊ณณ์ด ๋ฒฝ์ด ์๋๋ผ๋ฉด ๋ฑ์ ๋ค์ ์ ์ ์ ๋ฃ์ด์ค
chk[nx][ny] = chk[x][y] + 1;
dq.push_back({ nx, ny });
}
}
}
}
|
cs |
'๐ฅ PS(Problem Solving) ๐ฅ > goorm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๊ตฌ๋ฆLEVEL] ํํ (0) | 2020.04.01 |
---|---|
[๊ตฌ๋ฆLEVEL] ๋ง๊ฐ์ง ์๋ผํ ์คํ ๋ค์ค์ ์ฒด (0) | 2020.03.27 |
[๊ตฌ๋ฆLEVEL] ๋ฏธ๋ก์ฐพ๊ธฐ (0) | 2020.03.24 |
[๊ตฌ๋ฆLEVEL] ๋ณ๋ค์ ์ ์ (0) | 2020.03.24 |
[๊ตฌ๋ฆLEVEL] ์ ์ต์ (0) | 2020.03.23 |
๋๊ธ