반응형
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 |