백준 15558 : 점프 게임

문제 링크입니다 https://www.acmicpc.net/problem/15558

15558번: 점프 게임

총 2개의 줄로 나누어진 지도가 주어지고, 게임을 진행할 때, 게임을 클리어 할 수 있는지, 없는지 구하는 문제였습니다. 이동이 가능한 경우 큐에 넣고, 가능하지 않으면 다음 경우를 보는 방식의 BFS를 통해 구현했고, 자세한 문제 해결 절차는 다음과 같습니다.

 

[1] 문제의 게임에서 왼쪽, 오른쪽 두 줄을 2차원 배열 0번줄, 1번줄로 생각할 수 있으니 2 x N 배열을 선언하고 그 배열에 주어진 지도를 입력받습니다.

→ 코드상에서는 배열의 0번줄 -> 1번줄, 1번줄 -> 0번줄로 점프하는 것으로 생각하면 됩니다.

 

[2] 방문을 처리할 배열과 큐를 만들어 BFS를 시작합니다. 가능한 행동 세 가지에 대한 next 배열을 만들어 for문을 통해 세 가지 이동을 각각 해보고, 가능하다면 큐에 넣고 방문 처리 및 게임 시간을 +1 해줍니다.

 

[3] [2]를 반복하다가 다음칸으로 이동할 배열의 열 좌표가 N보다 크거나 같은 경우를 발견하면 게임을 CLEAR 할 수 있으므로 1을 출력하고, CLEAR 하는 경우가 발생하지 않고 BFS가 다 끝나면 0을 출력하도록 합니다.

 

더 자세한 구현 설명은 주석을 참고해주세요!

 

 

[소스코드]

 

#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 100000 + 1;
 
// 게임 지도에 해당하는 jump 배열
// 게임 시간을 저장할 time 배열
int n, k, jump[2][MAX], time[2][MAX];
 
// 게임에서 가능한 행동 3가지에 해당하는 위치를 이동 가능한지
// 판단하고 이동이 가능하다면 큐에 넣는 방식으로 BFS를
// 수행하고 게임을 CLEAR 하면 1, 못하면 0을 출력하는 함수
void solve_bfs(void) {
 
    bool check[2][MAX] = { 0, }; // 방문처리 배열
    queue <pair<int, int>> q;    
 
    check[0][0] = true;
    q.push(make_pair(0, 0));
 
    // 다음칸으로 이동할 수 있는 세가지 경우입니다
    // 행은 그대로 열만 +1, -1 혹은 행을 바꾸고 열을 +k
    pair <int, int> next[3] = { {0,1}, {0,-1}, {1, k} };
 
    while (!q.empty()) {
        int r = q.front().first, c = q.front().second;
        q.pop();
 
        // next에 저장된 세 가지 이동을 탐색합니다
        for (int i = 0; i < 3; i++) {
 
            // '% 2'를 하는 이유는 세 번째 행동에서
            // 행을 점프하기 위함입니다
 
            // 1번 행이었는데 next[2].first를 더하면 2가 되므로 
            // 연산 후 0이 되고
            
            // 0번 행이었는데 next[2].first를 더하면 1이 되므로
            // 연산 후 1이 됩니다
            int rr = (r + next[i].first) % 2;
            int cc = c + next[i].second;
 
            // 열 좌표가 n을 넘었으므로 clear
            if (cc >= n) {
                printf("1");
                return;
            }
            // 열 좌표가 음수이거나, 다음 칸이 이미 방문한 칸이라면
            if (cc < 0 || check[rr][cc]) continue;
 
            // 열 좌표가 이번 턴에 없어지는 열의 좌표보다 작거나
            // 이동하려는 칸이 위험한 칸(0)이라면
            if (cc < time[r][c] + 1 || !jump[rr][cc]) continue;
            
            // 방문처리 및 큐에 넣어주고 게임시간을 늘려줍니다
            check[rr][cc] = true;
            q.push(make_pair(rr, cc));
            time[rr][cc] = time[r][c] + 1;
        }
    }
    printf("0"); // can't clear
}
 
int main(void) {
 
    scanf("%d%d", &n, &k);
    
    // [1] i = 0 : 왼쪽 줄, i = 1 : 오른쪽 줄
    for (int i = 0; i < 2; i++)          
        for (int j = 0; j < n; j++)
            scanf("%1d", &jump[i][j]);
    solve_bfs();
    return 0;
}