[C++] 백준 1697 숨바꼭질

문제 링크

---

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

1697번: 숨바꼭질

 

접근 방법

---

어떤 지점에 도달하는데 있어 최초로 도달한 시간을 기록하는 문제이기에 BFS를 사용해야겠다고 떠올렸다.

 

(1) 변수

 visited[i]는 i에 도달하였을때의 시간을 기록해두며, 방문 여부도 동시에 판단할 수 있게 한다.

next[i]는 다음으로 이동할 지점이다.     

 

(2) 풀이

  다음 이동할 지점을 기록한 next[i] 가 도착지점(to)에 최초 도달할 때(visited[next[i]]가 -1인 상태) visited[now] + 1을

반환하면 된다.                                                                               

소스 코드

---

 

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

int visited[100001];

int bfs(int from, int to) {
	queue <int> q;
	q.push(from);
	visited[from] = 0;

	while (!q.empty()) {
		int now = q.front();
		int next[3] = { now + 1, now - 1, now * 2 };
		q.pop();
		for (int i = 0; i < 3; i++) 			
			if (0 <= next[i] && next[i] <= 100000 && visited[next[i]] == -1) {
				if (next[i] == to) return visited[now] + 1;
				q.push(next[i]);
				visited[next[i]] = visited[now] + 1;
			}
	}
	return 0;
}

int main() {
	int from, to;
    memset(visited, -1, sizeof(visited));
	cin >> from >> to;
	cout << bfs(from, to);
}

개발 환경 : VS 2019

질문, 지적 환영입니다.