https://www.algospot.com/judge/problem/read/JUMPGAME
๋ฌธ์
๋ ๋ฐ๋จน๊ธฐ๋ฅผ ํ๋ค ์ง๋ฆฐ ์ฌํ์ ์ํ์ด๋ ๋ ๋ฐ๋จน๊ธฐ์ ๋ณ์ข ์ธ ์๋ก์ด ๊ฒ์์ ํ๊ธฐ๋ก ํ์ต๋๋ค. ์ด ๊ฒ์์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด n*n ํฌ๊ธฐ์ ๊ฒฉ์์ ๊ฐ 1๋ถํฐ 9 ์ฌ์ด์ ์ ์๋ฅผ ์ด ์ํ๋ก ์์ํฉ๋๋ค. ๊ฐ ์ฐจ๋ก์ธ ์ฌ๋์ ๋งจ ์ผ์ชฝ ์ ์นธ์์ ์์ํด ์ธ๋ฐ๋ก ๋ฐ์ด์ ์ค๋ฅธ์ชฝ ์๋ ์นธ์ผ๋ก ๋ด๋ ค๊ฐ์ผ ํฉ๋๋ค. ์ด ๋ ๊ฐ ์นธ์ ์ ํ ์๋ ์ซ์๋งํผ ์ค๋ฅธ์ชฝ์ด๋ ์๋ ์นธ์ผ๋ก ์์ง์ผ ์ ์์ผ๋ฉฐ, ์ค๊ฐ์ ๊ฒ์ํ ๋ฐ์ผ๋ก ๋ฒ์ด๋๋ฉด ์ ๋ฉ๋๋ค.
๊ท ํ์ ์์ด์ ๋ค๋ฅธ ๋ฐ๋ก ์๊ฑฐ๋ ๋์ด์ ธ๋ ๊ฒ์์์ ์ง๋๋ค๋ง, ์ฌํ์ ์ํ์ด๋ ์ ๊ณ ํ๊ธฐ์ฐจ๊ธฐ ๋๋ฌธ์ ์ธ๋ฐ๋ก ๋ฐ์ด๋ค๋๋ ๊ฒ์ ์๋ฌด๊ฒ๋ ์๋๋๋ค. ๋ค๋ง ๊ฑฑ์ ๋๋ ๊ฒ์ ์ฃผ์ด์ง ๊ฒ์ํ์ ์์์ ์์ ๋์ ์ผ๋ก ๊ฐ๋ ๋ฐฉ๋ฒ์ด ์กด์ฌํ์ง ์์ ์๋ ์๋ค๋ ๊ฒ์ ๋๋ค. ์๋ฅผ ๋ค์ด ๊ทธ๋ฆผ (a)์ ๊ฒ์ํ์์๋ ์ฌ๊ฐํ์ผ๋ก ํ์๋ ์นธ๋ค์ ํตํด ๋์ ๋๋ฌํ ์ ์์ง๋ง, ์ซ์๊ฐ ํ๋ ๋ฐ๋ ๊ทธ๋ฆผ (b)์์๋ ๊ทธ๋ด ์๊ฐ ์์ต๋๋ค.
๊ฒ์ํ์ด ์ฃผ์ด์ง ๋ ์ผ์ชฝ ์์ ์์์ ์์ ์ค๋ฅธ์ชฝ ์๋์ ์์์ ์ ๋๋ฌํ ์ ์๋ ๋ฐฉ๋ฒ์ด ์๋์ง ํ์ธํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ธ์.
์ ๋ ฅ
์ ๋ ฅ์ ์ฒซ ์ค์๋ ํ ์คํธ ์ผ์ด์ค์ ์ C(C <= 50)๊ฐ ์ฃผ์ด์ง๋๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ ์ค์๋ ๊ฒฉ์์ ํฌ๊ธฐ n(2 <= n <= 100)์ด ์ฃผ์ด์ง๊ณ , ๊ทธ ํ n์ค์ ๊ฐ n๊ฐ์ ์ซ์๋ก ์ผ์ชฝ ์๋ถํฐ ๊ฐ ์นธ์ ์ฐ์ธ ์ซ์๋ค์ด ์ฃผ์ด์ง๋๋ค. ์ค๋ฅธ์ชฝ ์๋ ์๋ ๋ ์ ์์น์๋ 0์ด ์ฃผ์ด์ง๋๋ค.
์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค๋ง๋ค ํ ์ค๋ก, ์์์ ์์ ๋ ์ ์ผ๋ก ๋๋ฌํ ์ ์์ ๊ฒฝ์ฐ "YES"๋ฅผ, ์๋ ๊ฒฝ์ฐ "NO"๋ฅผ ์ถ๋ ฅํฉ๋๋ค. (๋ฐ์ดํ ์ ์ธ)
๋์ ๋ต
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int main() {
int test_case;
cin >> test_case;
while (test_case--) {
int n;
cin >> n;
int** arr = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
arr[i] = (int*)malloc(n * sizeof(int));
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
queue<pair<int, int>> num_q;
num_q.push(make_pair(0, 0));
vector<vector<int>> check(n, vector<int>(n));
while (num_q.size()) {
int y = num_q.front().first; int x = num_q.front().second;
num_q.pop();
check[y][x] = 1;
if (y == (n - 1) && x == (n - 1))
break;
int jump = arr[y][x];
if (y + jump < n && !check[y + jump][x]) // ์๋์ชฝ
num_q.push(make_pair(y + jump, x));
if (x + jump < n && !check[y][x + jump]) // ์ค๋ฅธ์ชฝ
num_q.push(make_pair(y, x + jump));
}
if (check[n - 1][n - 1])
cout << "YES";
else
cout << "NO";
}
}
์ผ๋จ ์์ผ๋ก ์๊ณ ๋ฆฌ์ฆ์ ์งค ๋, Queue๋ฅผ ์ด์ฉํ bfs๋ฅผ ํ์ฉํด์ผ๊ฒ ๋ค๋ ์๊ฐ์ ํ๊ณ queue์ ๋ค์ด๊ฐ ์ ์๋ ์์น์ ์กฐ๊ฑด์ ๋งต ์์ด๊ณ , ์์ง ๋ค๋ฅด์ง ์์ ๊ณณ์ด์๋ค. ๋ํ ๊ธฐ์ ์ฌ๋ก๋ queue๊ฐ ๋น๊ฑฐ๋ ๋์ ๋ค๋ค๋ฅธ ๊ฒฝ์ฐ์ด๋ค.
์์์ ๊ตฌํ ํจํด์ ์๊ฐํด๋ดค๋ฏ์ด ๊ธฐ์ ์ฌ๋ก์ธ queue๊ฐ ๋น๊ฑฐ๋ ๋์ ๋ค๋ค๋ฅธ ๊ฒฝ์ฐ๋ ์๋ถ๋ถ์ ๋ฐฐ์นํ์ฌ ์ค๋ฅ๊ฐ ์๋๋ก ํ์๊ณ , memset์ ์ฌ์ฉํ ์๊ฐ์ ๋ชปํ์๋๋ฐ ๋ค๋ฅธ ๊ณณ์ ์ฒดํฌํ๋ check์ ์๋ฃ๊ตฌ์กฐ๋ฅผ 2์ฐจ์ vector๋ก ์ ์ํ์ฌ ์๋ ์ด๊ธฐํํ๊ธฐ ์ฌ์์ ๊ด์ฐฎ์๋ค.
์ฌ๊ท ํธ์ถ์์ ์์ํ๊ธฐ
์ฑ ์์๋ ์ฌ๊ท ํธ์ถ์ ๊ตฌํํ ํ, ๋ฉ๋ชจ์ด์ ์ด์ ์ ํตํด ์ค๋ณต๋๋ ๊ฒฝ์ฐ๋ฅผ ์ ๊ฑฐํ์๋ค. ๋ฐ๋ผ์ bfs ๋ฐฉ์์ ์ด ๋ณธ์ธ๊ณผ๋ ์กฐ๊ธ์ ์ฐจ์ด๊ฐ ์์๋ค.
Comment