반응형

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

 

15558번: 점프 게임

첫째 줄에 N과 k가 주어진다. (1 ≤ N, k ≤ 100,000) 둘째 줄에는 왼쪽 줄의 정보가 주어진다. i번째 문자가 0인 경우에는 위험한 칸이고, 1인 경우에는 안전한 칸이다. 셋째 줄에는 오른쪽 줄의 정보

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. string arr[2] 배열을 만들어 지도를 저장하고, visited 배열을 만들어 각 위치의 방문 여부를 저장합니다.

 

2. 지도에서 1인 지역만 방문하면서 N보다 큰 좌표로 이동할 수 있으면 1을, 그렇지 않으면 0을 출력합니다.  

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<queue>
#include<string>
 
using namespace std;
 
int N, k;
int visited[2][100000];
 
struct node {
    int pos;
    int cnt;
    bool isLeft;
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> k;
 
    string arr[2];
    cin >> arr[0] >> arr[1];
 
    queue<node> q;
 
    q.push({ 0,0,true });
    visited[0][0] = 1;
 
    while (!q.empty()) {
        const int pos = q.front().pos;
        const int cnt = q.front().cnt;
        const bool isLeft = q.front().isLeft;
        q.pop();
 
        if (pos + k >= N || pos == N - 1) {
            cout << 1;
            return 0;
        }
 
        if (isLeft == true) {
            if (pos - 1 > cnt && arr[0][pos - 1] == '1' && visited[0][pos - 1] != 1) {
                visited[0][pos - 1] = 1;
                q.push({ pos - 1,cnt + 1,true });
            }
            if (arr[0][pos + 1] == '1' && visited[0][pos + 1] != 1) {
                visited[0][pos + 1] = 1;
                q.push({ pos + 1,cnt + 1,true });
            }
            if (arr[1][pos + k] == '1' && visited[1][pos + k] != 1) {
                visited[1][pos + k] = 1;
                q.push({ pos + k,cnt + 1,false });
            }
        }
        else {
            if (pos - 1 > cnt && arr[1][pos - 1] == '1' && visited[1][pos - 1] != 1) {
                visited[1][pos - 1] = 1;
                q.push({ pos - 1,cnt + 1,false });
            }
            if (arr[1][pos + 1] == '1' && visited[1][pos + 1] != 1) {
                visited[1][pos + 1] = 1;
                q.push({ pos + 1,cnt + 1,false });
            }
            if (arr[0][pos + k] == '1' && visited[0][pos + k] != 1) {
                visited[0][pos + k] = 1;
                q.push({ pos + k,cnt + 1,true });
            }
        }
    }
 
    cout << 0;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 16954번 - 움직이는 미로 탈출 (C++)  (0) 2023.07.29
[ 백준 ] 16509번 - 장군 (C++)  (0) 2023.07.28
[ 백준 ] 1245번 - 농장 관리 (C++)  (0) 2023.07.26
[ 백준 ] 16934번 - 게임 닉네임 (C++)  (0) 2023.07.25
[ 백준 ] 7432번 - 디스크 트리 (C++)  (0) 2023.07.24

+ Recent posts

티스토리툴바