[BFS] 15558번 점프게임

15558번 점프 게임

 

https://www.acmicpc.net/problem/15558

 

문제

상근이는 아래의 그림과 같은 지도에서 진행하는 게임을 만들었다.

|   N   |	|   N   |
|  N-1  |	|  N-1  |
|   .   |	|   .   |
|   .   |	|   .   |
|   .   |	|   .   |
|   3   |	|   3   |
|   2   |	|   2   |
|   1   |	|   1   |

 

지도는 총 2개의 줄로 나누어져 있으며, 각 줄은 N개의 칸으로 나누어져 있다. 칸은 위험한 칸과 안전한 칸으로 나누어져 있고, 안전한 칸은 유저가 이동할 수 있는 칸, 위험한 칸은 이동할 수 없는 칸이다.

가장 처음에 유저는 왼쪽 줄의 1번 칸 위에 서 있으며, 매 초마다 아래 세 가지 행동중 하나를 해야 한다.

• 한 칸 앞으로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i+1번 칸으로 이동한다.
• 한 칸 뒤로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i-1번 칸으로 이동한다.
• 반대편 줄로 점프한다. 이때, 원래 있던 칸보다 k칸 앞의 칸으로 이동해야 한다. 예를 들어, 현재 있는 칸이 왼쪽 줄의 i번 칸이면, 오른쪽 줄의 i+k번 칸으로 이동해야 한다.

N번 칸보다 더 큰 칸으로 이동하는 경우에는 게임을 클리어한 것이다.

게임을 재밌게 하기 위해서, 상근이는 1초에 한 칸씩 각 줄의 첫 칸이 사라지는 기능을 만들었다. 즉, 게임을 시작한지 1초가 지나면 1번 칸이 사라지고, 2초가 지나면 2번 칸이 사라진다. 편의상 유저가 먼저 움직이고, 칸이 사라진다고 가정한다. 즉, 이번에 없어질 칸이 3번 칸인데, 상근이가 3번 칸에 있다면, 3번 칸에서 다른 칸으로 이동하고 나서 3번 칸이 없어지는 것이다.

각 칸의 정보가 주어졌을 때, 게임을 클리어 할 수 있는지, 없는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 k가 주어진다. (1 ≤ N, k ≤ 100,000)

둘째 줄에는 왼쪽 줄의 정보가 주어진다. i번째 문자가 0인 경우에는 위험한 칸이고, 1인 경우에는 안전한 칸이다. 셋째 줄에는 오른쪽 줄의 정보가 주어지고, 각 문자의 의미는 왼쪽 줄의 의미와 동일하다.

왼쪽 줄의 1번 칸은 항상 안전한 칸이다.

 

출력

게임을 클리어할 수 있으면 1을, 없으면 0을 출력한다.

 

예제 입력

7 3
1110110
1011001

23 5
10000000100010010000000
00011111001111111100100

 

예제 출력

1

1

 

해결방법

BFS 탐색을 통해 맵 밖으로 나갈 수 있는지 탐색하는 문제이다

처음에는 중복방문을 처리해주지 않아 메모리초과 가 발생했다가 중복을 처리하였다

 

⭐️ 솔루션 ⭐️

• N ≤ 100
• 시간 복잡도 : O(2 * 100,000)

 

한 노드에서 할 수 있는 행동은 아래와 같다

1. 앞으로 한칸 이동
2. 뒤로 한칸 이동
3. 옆으로 이동 후, K칸 이동

 

사실 노드에서 몇 가지 방법으로 이동하는 거야 어렵지 않았다

하지만 중복 방문이 헷갈렸다

계속 생각을 하다가 생각이 정리가 되었다!!

기본 BFS 탐색을 수행한다고 가정해보자

• (0,0) 에서 (n,m) 노드로 이동을 했다

• 그 후, (1,1) 에서 (n,m) 노드로 이동을 하려한다

이런 상황에서 (1,1) 은 (n,m) 으로 이동할 수 있을까?

• BFS 탐색은 최단 거리 탐색을 기초로 하고있다
• 따라서 (1,1) → (n,m) 으로의 이동 경로가 (0,0) → (n,m) 으로의 이동 경로보다 짧다면 이동할 필요가 없다
• 따라서 visited 배열을 통해 중복 방문을 방지하는 것이다

 

 

또한 MAX 의 범위에 주의해야한다

n,k 를 100,000 이라고 가정해보자

만약 현재 위치가 (0,99999) 이고 옆 칸으로 이동 후, k칸 만큼 이동한다면?

이동 후의 위치는 (1,199999) 가 될 것이다

따라서 이동 가능 좌표는 0 ~ k + n - 1 이다

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <queue>
#include <algorithm>
#define MAX 200001
#define INF 987654321
using namespace std;

struct node {
    int x,y,remove;
    
    node() { }
    node(int _x,int _y,int _remove) : x(_x),y(_y),remove(_remove) { }
};

int n,k;

int map[2][MAX];
bool visited[2][MAX];

void bfs(){
    queue<node> q;
    q.push(node(0,0,-1));
    
    while(!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int remove = q.front().remove;
        q.pop();
        
        // 칸이 사라져 이동하지 못하는 경우
        if(y <= remove){
            continue;
        }
        
        // 앞으로 한칸 이동하는 경우
        if(map[x][y+1] == 1 && !visited[x][y+1]){
            q.push(node(x,y+1,remove+1));
            visited[x][y+1] = true;
        }
        
        // 뒤로 한칸 이동하는 경우
        if(y-1 >= 0 && map[x][y-1] == 1 && !visited[x][y-1]){
            q.push(node(x,y-1,remove+1));
            visited[x][y-1] = true;
        }
        
        bool flag = false;
        int nx = x==0 ? 1 : 0;
        // 옆으로 k칸 이동하는 경우
        if(y+k >= n){
            flag = true;
        }
        else if(map[nx][y+k] == 1 && !visited[nx][y+k]){
            q.push(node(nx,y+k,remove+1));
            visited[nx][y+k] = true;
        }
        
        // 탈출한 경우
        if(flag){
            cout << 1 << "\n";
            return;
        }
    }
    cout << 0 << "\n";
    return;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL); cout.tie(NULL);
    
    scanf("%d %d",&n,&k);
    for(int i=0; i<2; i++){
        for(int j=0; j<n; j++){
            scanf("%1d",&map[i][j]);
        }
    }
    
    bfs();
    
    return 0;
}