[백준 1697번] 숨바꼭질
2020. 5. 22. 18:54ㆍAlgorithm/practice
https://www.acmicpc.net/problem/1697
struct Node를 정의하여 자료형 Node인 graph를 만들고자 했다. struct Node에서 x는 노드번호를 의미한다. 이 문제를 BFS로 해결하고자 했기 때문에 ★Node의 time은 bfs에서 해당 노드의 depth★를 의미한다.
struct Node {
int x, time;
};
자료형 bool인 배열 visited를 두어 노드의 방문여부를 체크한다. 수빈이가 지나간 노드를 true로 체크한다. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간 time을 구해야하기 한다. 처음 방문한 노드만 queue에 추가해준다.
#include <stdio.h>
#include <queue>
#define MAX_N 200001
using namespace std;
bool visited[MAX_N];
int X[3] = { 1,-1, 2 };
queue <Node> q;
struct Node {
int x, time;
};
int bfs(int x, int tx) {
Node currNode = {x, 0};
q.push(currNode);
visited[x] = true;
while (!q.empty()) {
currNode = q.front();
q.pop();
if (currNode.x == tx) {
return currNode.time;
}
int nextNode = -1;
for (int i = 0; i < 3; i++) {
if (i == 2) {
nextNode = currNode.x * X[i];
}
else {
nextNode = currNode.x + X[i];
}
if (nextNode <0 || nextNode > 200000) {
continue;
}
if (visited[nextNode] == false) {
visited[nextNode] = true;
q.push({ nextNode, currNode.time + 1 });
}
}
}
}
int main() {
int n, m, num;
scanf("%d %d", &n, &m);
printf("%d", bfs(n, m));
return 0;
}
'Algorithm > practice' 카테고리의 다른 글
[백준 2523번] 별찍기-13 (0) | 2020.07.08 |
---|---|
[백준 1110번] 더하기 사이클 (0) | 2020.07.08 |
[백준 10996번] 별찍기-21 (0) | 2020.07.08 |
[백준 9093] 단어 뒤집기 (0) | 2020.07.02 |
[백준 11279번] 최대 힙 (0) | 2020.05.28 |