https://www.acmicpc.net/problem/16928
16928번: 뱀과 사다리 게임
첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으
www.acmicpc.net
이 문제의 경우 생각해줘야할 게 많았다 일반 Bfs지만 문제를 잘 읽지 않으면 틀린다
이문제에서 간과하면 안될 조건이 있다.
1. 시작점에 사다리와 뱀이 여러개 놓일 수는 없지만 도착점은 상관없다.
2. 뱀과 사다리를 만나면 무조건 이동한다 이다 즉 발판을 밟지 못한다.
이 위를 생각하고 풀어야 빠른시간안에 풀 수 있었다 필자는 이 부분을 캐치하지 못 해 오랜시간이 걸렸다.
#include <iostream>
#include <queue>
using namespace std;
int arr[101];
int visited[101];
int radder[101];
queue<int> bfsq;
int solution() {
bfsq.push(1);
while (!bfsq.empty()) {
int start = bfsq.front();
bfsq.pop();
if ((start + 6 <= 100) && !visited[start + 6]) {
if (radder[start + 6] > 0) {
if (visited[radder[start + 6]] == 0) {
visited[radder[start + 6]] = visited[start] + 1;
bfsq.push(radder[start + 6]);
}
}
else if (radder[start + 6] == 0) {
visited[start + 6] = visited[start] + 1;
bfsq.push(start + 6);
}
if (start + 6 == 100)
return visited[start + 6];
}
if ((start + 5 <= 100) && !visited[start + 5]) {
if (radder[start + 5] > 0) {
if (visited[radder[start + 5]] == 0) {
visited[radder[start + 5]] = visited[start] + 1;
bfsq.push(radder[start + 5]);
}
}
else if (radder[start + 5] == 0) {
visited[start + 5] = visited[start] + 1;
bfsq.push(start + 5);
}
if (start + 5 == 100)
return visited[start + 5];
}
if ((start + 4 <= 100) && !visited[start + 4]) {
if (radder[start + 4] > 0) {
if (visited[radder[start + 4]] == 0) {
visited[radder[start + 4]] = visited[start] + 1;
bfsq.push(radder[start + 4]);
}
}
else if (radder[start + 4] == 0) {
visited[start + 4] = visited[start] + 1;
bfsq.push(start + 4);
}
if (start + 4 == 100)
return visited[start + 4];
}
if ((start + 3 <= 100) && !visited[start + 3]) {
if (radder[start + 3] > 0) {
if (visited[radder[start + 3]] == 0) {
visited[radder[start + 3]] = visited[start] + 1;
bfsq.push(radder[start + 3]);
}
}
else if (radder[start + 3] == 0) {
visited[start + 3] = visited[start] + 1;
bfsq.push(start + 3);
}
if (start + 3 == 100)
return visited[start + 3];
}
if ((start + 2 <= 100) && !visited[start + 2]) {
if (radder[start + 2] > 0) {
if (visited[radder[start + 2]] == 0) {
visited[radder[start + 2]] = visited[start] + 1;
bfsq.push(radder[start + 2]);
}
}
else if (radder[start + 2] == 0) {
visited[start + 2] = visited[start] + 1;
bfsq.push(start + 2);
}
if (start + 2 == 100)
return visited[start + 2];
}
if ((start + 1 <= 100) && !visited[start + 1]) {
if (radder[start + 1] > 0) {
if (visited[radder[start + 1]] == 0) {
visited[radder[start + 1]] = visited[start] + 1;
bfsq.push(radder[start + 1]);
}
}
else if (radder[start + 1] == 0) {
visited[start + 1] = visited[start] + 1;
bfsq.push(start+1);
}
if (start + 1 == 100)
return visited[start + 1];
}
}
}
int main() {
int N, M;
cin >> N >> M;
for (int i = 0; i < N+M; i++) {
int from, to;
cin >> from>> to;
radder[from] = to;
}
cout << solution();
}코드가 길지만 사실 실제로 보면 얼마 안되는 양이다.
일단 주목해야할 부분은
if ((start + 6 <= 100) && !visited[start + 6]) {
if (radder[start + 6] > 0) {
if (visited[radder[start + 6]] == 0) {
visited[radder[start + 6]] = visited[start] + 1;
bfsq.push(radder[start + 6]);
}
}
else if (radder[start + 6] == 0) {
visited[start + 6] = visited[start] + 1;
bfsq.push(start + 6);
}
if (start + 6 == 100)
return visited[start + 6];
}이 부분이다 이부분의 경우느 일단 우리가 방문할려는 지점이 방문되었는지 또한 우리가 방문할 발판이 100을 넘었는지를 검사한다. 넘으면 실행 하지 않는다 그후 사다리나 뱀이 있다면 그 발판을 밟지 않고 이어져있는 발판을 밟는다 그 후 이를 bfs에 넣는다. 만약 사다리나 뱀이없으면 해당 발판을 밟는다. 이게 풀이 로직이었다.
코테에서 항상 중요한 점은 빠른시간안에 반례체킹을 하는 것인거 같다.