티스토리 뷰
https://www.acmicpc.net/problem/17071
17071번: 숨바꼭질 5
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
진짜 어려웠다. 한 2~3일? 고민했는데도 어려워서 질문 게시판 보고 힌트를 얻어서 풀었다.
엄청 깔끔하게 짠 코드는 아니지만 내 블로그 기록의 목적은 공부용이니까 우선 남겨둔다.
처음 내가 생각했던 방법은 다음과 같았다.
1. 수빈이를 BFS할 배열 subin과 동생을 BFS할 배열 brother를 각각 만들어서, 수빈이 1초, 동생 1초 이렇게 진행한다. 이 때 동생의 현재 위치 k는 따로 저장해둔다.
2. subin[k]와 brother[k]가 0이 아니면서(초기값이 0이므로) 둘 다 동일한 값이 들어가면 리턴하고 종료한다.
이렇게 생각해서 풀수 있을줄 알았는데, 예제 2번이 복병이었다.
예제 2번의 수빈이의 이동 순서는 17-18-17-16-15, 동생은 5-6-8-11-15였는데, BFS는 동일한 위치에 한 번만 방문하는게 조건이였기 때문이다.(이 조건을 어기고 여러 번 방문하면 큐에 너무 많은 원소가 들어와서 메모리 초과로 터진다)
이를 해결하기 위해서 다양한 방법을 써보다가 17-18-17은 0초,2초고 이는 같은 짝수나 홀수일 때라면 정답을 출력할 수 있겠구나 싶은 생각이 들었는데, 또 18 66이 문제더라.
18 66은 76에서 만나야 하는데, 수빈과 동생으로 나누니까 수빈이는 72에서 2초일때 값이 저장되고, 동생은 72가 3초일때 값이 저장되더라.
여기서 막혀서 좀 찾아보니까 짝수/홀수로 아예 나누는 방법이 있다는걸 알게 되었고, subin 배열을 odd,even으로 나누어서 저장해서 맞췄다.
결국 내가 풀었던 방법은 다음과 같았다.
1. 수빈이를 짝수/홀수로 나눠서 저장할 배열 odd,even과 동생을 BFS할 배열 brother를 만들어서, 수빈이 1초씩, 동생 1초씩 진행한다. 이때 동생의 현재 위치 k와 BFS를 진행한 시간 ksec는 따로 저장해둔다.
2. ksec가 홀수이고 odd[k]와 brother[k]에 값이 있거나 / ksec가 짝수이고 even[k]와 brother[k]에 값이 있으면 brother[k]를 리턴한다.
brother[k]를 리턴하는 이유는 간단하게 수빈이가 도착한 시간이 아닌 동생이 도착한 시간을 리턴해야 하기 때문이다.
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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | #include <iostream> #include <queue> using namespace std; #define MAX 500002 queue <pair<int, int>> q, sub; int odd[MAX], even[MAX], brother[MAX]; bool vis[MAX]; int n, k, ksec; void input() { cin >> n >> k; } int solve() { q.push({ n,0 }); sub.push({ k,0 }); if (n == k) { if (n > 500000) return -1; return 0; } while (!q.empty() || !sub.empty()) { if (k > 500000) return -1; if (ksec % 2 == 0 && even[k] != 0 && brother[k] != 0) // 현재 이동한 시간이 짝수 { return brother[k]; } else if (ksec % 2 == 1 && odd[k] != 0 && brother[k] != 0) // 현재 이동한 시간이 홀수 { return brother[k]; } int t = q.size(); while (t--) // 수빈 짝수/홀수로 나누기 { auto cur = q.front(); q.pop(); int x, sec; x = cur.first; sec = cur.second; sec++; // 여기서 1 증가시켜주는 이유는 if문장의 조건을 만족하기 위해서 if (sec % 2 == 1) // 위에서 증가시켜야 1초일때 홀수, 2초일때 짝수... 배열로 들어감 { if (x > 0 && odd[x - 1] == 0) { odd[x - 1] = sec; q.push({ x - 1,sec }); } if (x < 500000 && odd[x + 1] == 0) { odd[x + 1] = sec; q.push({ x + 1,sec }); } if (x > 0 && x * 2 <= 500000 && odd[x * 2] == 0) { odd[x * 2] = sec; q.push({ x * 2,sec }); } } else { if (x > 0 && even[x - 1] == 0) { even[x - 1] = sec; q.push({ x - 1,sec }); } if (x < 500000 && even[x + 1] == 0) { even[x + 1] = sec; q.push({ x + 1,sec }); } if (x > 0 && x * 2 <= 500000 && even[x * 2] == 0) { even[x * 2] = sec; q.push({ x * 2,sec }); } } } t = sub.size(); while (t--) // 동생 x+sec초 증가 { auto cur = sub.front(); sub.pop(); int x, sec; x = cur.first; sec = cur.second; if (brother[x + ++sec] == 0) { brother[x + sec] = sec; sub.push({ x + sec,sec }); k = x + sec; ksec = sec; } } } return -1; } int main() { cin.tie(0); ios::sync_with_stdio(0); input(); cout << solve(); } | cs |
'PS > 백준' 카테고리의 다른 글
(C++) [백준 3197번] 백조의 호수 (0) | 2022.07.20 |
---|---|
(C++) [백준 9328번] 열쇠 (0) | 2022.07.15 |
(C++) [백준 16920번] 확장 게임 (0) | 2022.07.04 |
(C++) [백준 16933번] 벽 부수고 이동하기 3 (0) | 2022.07.04 |
(C++) [백준 14442번] 벽 부수고 이동하기 2 (0) | 2022.06.30 |
- Total
- Today
- Yesterday
- 2493
- 6593
- 1475
- 2146
- 6603
- 1251
- PS
- 숨바꼭질 4
- 벽 부수고 이동하기 2
- BOJ
- 백준
- 구름톤챌린지
- 파핑파핑 지뢰찾기
- 3273
- 벽 부수고 이동하기 3
- 두 수의 합
- 3197
- 16933
- 9328
- 숨바꼭질 5
- 17071
- SWEA
- 상범 빌딩
- 5397
- 3190번
- 16920
- 2583
- 확장 게임
- 5427
- DX부문
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |