https://www.acmicpc.net/problem/1834
문제
> 상근이는 오른쪽 그림과 같은 지도에서 진행하는 게임을 만들었다.
> 지도는 총 2개의 줄로 나누어져 있으며, 각 줄은 N개의 칸으로 나누어져 있다.
> 칸은 위험한 칸과 안전한 칸으로 나누어져 있고,
안전한 칸은 유저가 이동할 수 있는 칸,
위험한 칸은 이동할 수 없는 칸이다.
> 가장 처음에 유저는 왼쪽 줄의 1번 칸 위에 서 있으며,
매 초마다 아래 세 가지 행동중 하나를 해야 한다.
> 한 칸 앞으로 이동한다.
예를 들어, 현재 있는 칸이 i번 칸이면, i+1번 칸으로 이동한다.
> 한 칸 뒤로 이동한다.
예를 들어, 현재 있는 칸이 i번 칸이면, i-1번 칸으로 이동한다.
> 반대편 줄로 점프한다. 이때, 원래 있던 칸보다 k칸 앞의 칸으로 이동해야 한다.
예를 들어, 현재 있는 칸이 왼쪽 줄의 i번 칸이면, 오른쪽 줄의 i+k번 칸으로 이동해야 한다.
> N번 칸보다 더 큰 칸으로 이동하는 경우에는 게임을 클리어한 것이다.
> 게임을 재밌게 하기 위해서, 상근이는 1초에 한 칸씩 각 줄의 첫 칸이 사라지는 기능을 만들었다.
> 즉, 게임을 시작한지 1초가 지나면 1번 칸이 사라지고, 2초가 지나면 2번 칸이 사라진다.
> 편의상 유저가 먼저 움직이고, 칸이 사라진다고 가정한다.
> 즉, 이번에 없어질 칸이 3번 칸인데, 상근이가 3번 칸에 있다면, 3번 칸에서 다른 칸으로 이동하고 나서 3번 칸이 없어지는 것이다.
> 각 칸의 정보가 주어졌을 때, 게임을 클리어 할 수 있는지, 없는지 구하는 프로그램을 작성하시오.접근
지도를 이차원 벡터에 표현하는데 (N,2)의 크기로 만든다. N은 칸수, 2는 왼쪽과 오른쪽 줄을 나타낸다.
상근이가 이동 할 수 있는 세가지 방법을 현재의 좌표기준으로 정의한다. 전진은 +1, 후진은 -1, 점프는 +k, (현줄+1)%2로 구한다. 새롭게 구한 좌표에 대해 안전한 칸인 1인지, 이미 갔다왔던 칸인지, 흐른 시간인 초 보다 큰지를 확인한다. 이 모두를 만족하면 갈 수 있으므로 큐에 넣어 다음경로를 탐색한다.
이과정을 반복하다 새로운 좌표가 N을 넘어가면 클리어, 넘어가지 못하고 큐가 끝나면 0으로 미클리어된다.
문제해결
> 지도를 나타낼 이차원 벡터 foot을 선언해 크기를 N,2로 만든다.(N칸, 2줄)
> 특정칸에서의 반복이동을 제하기 위해 방문처리 벡터도 선언해준다.
> 큐에 칸, 줄, 초의 정보를 담아 넣을 것이므로 이를 state라는 struct로 만들어준다.
> 이제 점프게임JG메소드에 인자로 시작칸, 시작줄, 시작초를 받아 시작한다.
> 그래프탐색을 하며 각 동작마다 조건문으로 나누어 처리한다.
> 각각의 동작을 처리하기 전에 새로갈 위치의 칸수를 먼저구하고 N을 넘어가면(클리어가능한지) 클리어처리 해준다.
> 각각 새로구한 좌표가 1로 안전한 칸인지, 아직 안갔던 칸인지를 확인하고, 현재까지 흐른시간보다 큰지를 확인한다.
> 현재까지이 초 보다 작거나 같은 칸을 가게 된다면 해당 위치에 갔을 때 발판이 사라져버린다.
> main함수에서 시작점 1,0위치에서 1초부터 시작하므로 이를 넣어 호출해준다.코드
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int N, K;
vector<vector<int>> foot;
vector<vector<bool>> visited;
struct state
{
int pos, line, time;
};
int JG(int sp, int sl, int st)
{
queue<state> q;
q.push({ sp, sl, st });
visited[sp][sl] = true;
while (!q.empty())
{
int fp = q.front().pos;
int fl = q.front().line;
int ft = q.front().time;
q.pop();
int fnp = fp + 1, jnp = fp + K;
int jnl = (fl + 1) % 2; // 삼항, 1에서 빼기
if (fnp > N || jnp > N) return 1;
if (foot[fnp][fl] == 1 && !visited[fnp][fl] && fnp > ft)
{
q.push({ fnp, fl, ft + 1 });
visited[fnp][fl] = true;
}
if (foot[fp - 1][fl] == 1 && !visited[fp - 1][fl] && fp-1 > ft)
{
q.push({ fp - 1, fl, ft + 1 });
visited[fp - 1][fl] = true;
}
if (foot[jnp][jnl] == 1 && !visited[jnp][jnl] && jnp > ft)
{
q.push({ jnp, jnl, ft + 1 });
visited[jnp][jnl] = true;
}
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> K;
foot.resize(N + 1, vector<int>(2));
visited.assign(N + 1, vector<bool>(2, false));
for (int i = 0; i < 2; i++)
{
string str;
cin >> str;
for (int j = 1; j <= N; j++) foot[j][i] = str[j-1] - '0';
}
cout << JG(1, 0, 1) << '\n';
}
후기
방문처리를 왜 할까 했는데 생각해보면 N이 커지면 점프점프로 쭉 앞에가서 초가 따라잡기 까지 같은칸을 왔다갔다하는 문제가 생길 수 있어서 그렇다.
또 발판 사라짐의 동작이 헷갈려서 전부 출력해보면서 해봤다. 두번째 예제가 가능하다고 나와서 문제를 찾아보니
시작 초를 0으로 줘서그랬다. 그렇게 되면 칸은 1부터 시작하므로 1초가 밀린게 된다. 예를 들어 1에서 점프해 3으로 가고 후진해서 2로 가면 총 2초가 흐른거라 후진 칸 2와 초 2가 같아 갈 수 없는데 0으로 시작하면 초가 현재 1인 상태라 가능하게 나온다.
