https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
1) 풀이
이전에 풀이했던 BFS 문제들과는 다르게, 이번엔 일차원 배열에서 행해지는 bfs 문제이다.
어떻게 보면 이차원 배열보다 비교적 간단하다고 할 수 있다.
수빈이와 동생이 위치하고 있는 지점은 배열의 인덱스로 생각하면 된다.
숨바꼭질하는 판(board)과 수빈이가 동생을 찾는 시간을 저장하는 배열을 따로 둘 필요없이
그냥 수빈이가 이동하는 좌표(인덱스)에 값으로 시간을 저장하면 된다.
board를 처음에 모두 -1로 초기화해두고 수빈이가 출발하는 지점 n 인덱스의 값은 0으로 지정해두고
수빈이가 위치를 옮길 때마다 이전 칸의 값에서 1을 더해주면, 수빈이가 그 칸에 방문했는지에 대한 여부도
체크할 수 있다.
(수빈이가 칸을 옮길 때 모두 1초가 소요되므로 1을 더하는 것)
그렇게 수빈이가 칸을 옮길 때마다 그 칸에 도착했을 때 소요한 총 시간을 넣어주는 작업을 하다보면,
동생이 위치한 k칸에 도달했을 때, k 값도 기존에 초기화돼있던 -1에서 바뀌게 된다.
이것을 탐색 반복문의 종료조건으로 넣어주면, 수빈이가 동생을 찾았을 때 탐색이 바로 종료될 수 있다!!
이전과 같이 수빈이가 이동하는 좌표를 저장하는 queue 가 빌 때까지 를 조건으로 넣어버리면,
수빈이가 동생을 찾았음에도 이동을 멈추지 않아 최단 시간을 구하기 힘들어질 수 있다.
딱히 어려운 점은 없었던 문제!
2) 최종 소스코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int board[100002];
int x[3] = { 1,-1,2 };
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
fill(board, board + 100002, -1);
queue<int>q; //수빈이가 이동하는 좌표 저장
q.push(n);
board[n] = 0; //수빈이가 출발하는 지점을 0
while (board[k] == -1) { //k가 -1에서 바뀌는 순간 수빈이가 동생을 찾은 것
int cur = q.front();
q.pop();
for (int i : {cur + 1, cur - 1, cur * 2}) {
if (i < 0 || i>100000) continue; //범위 벗어남
if (board[i] >= 0) continue; //수빈이가 이미 지나간 곳
q.push(i);
board[i] = board[cur] + 1; //한칸 이동하는 데에 1초 걸리므로 이전칸보다 1더해주기
}
}
cout << board[k];
}
3) 참고자료
'Problem Solving > 백준' 카테고리의 다른 글
[프로그래머스/JavaScript] 구명보트 (0) | 2022.11.12 |
---|---|
[백준/c++] 1012 - 유기농 배추 (0) | 2021.06.06 |
[백준/c++] 4179 - 불! (0) | 2021.06.04 |
[백준/c++] 2178 - 미로 탐색 (0) | 2021.06.01 |
[백준/c++] 7576 - 토마토 (0) | 2021.06.01 |