일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- springboot
- JPA
- 자료 구조
- Vue
- 스택
- 구현
- 정보처리기사
- Spring Security
- 문자열
- 깊이 우선 탐색
- 다이나믹 프로그래밍
- 백트래킹
- 너비 우선 탐색
- 프로그래머스
- MYSQL
- 정수론
- 알고리즘
- dfs
- 소수 판정
- 수학
- 프로젝트
- 백준
- 재귀
- 그래프 이론
- DB
- 그래프 탐색
- n과 m
- 배포
- SWEA
- 브루트포스 알고리즘
Archives
- Today
- Total
영원히 남는 기록, 재밌게 쓰자
백준 [1697] 숨바꼭질 본문
728x90
반응형
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
풀이
수빈이가 움직일 수 있는 이동할 수 있는 조건인
한 칸 뒤로 움직일 때 (x-1), 한 칸 앞으로 움직일 때 (x + 1), 순간이동을 하는 경우 (x * 2)로 나누면 현재 위치에서 이동할 수 있는 가장 가까운 노드이므로 BFS 탐색이 효율적일 것 같다고 생각하였다.
정답 코드
package com.baekjoon.p1697;
import java.io.*;
import java.util.*;
public class Main {
static int[] arr = new int[100001];
static int n, k;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
bfs(n);
System.out.println(arr[k]);
}
private static void bfs(int val) {
Queue<Integer> q = new LinkedList<>();
q.add(val);
while (!q.isEmpty()) {
int temp = q.remove();
if (temp == k) {
return;
}
int back = temp - 1;
int front = temp + 1;
int jump = temp * 2;
if (back >= 0 && arr[back] == 0) {
q.add(back);
arr[back] = arr[temp] + 1;
}
if (front <= 100000 && arr[front] == 0) {
q.add(front);
arr[front] = arr[temp] + 1;
}
if (jump <= 100000 && arr[jump] == 0) {
q.add(jump);
arr[jump] = arr[temp] + 1;
}
}
}
}
Github:
728x90
반응형
'Algorithm > 백준' 카테고리의 다른 글
백준 [13913] 숨바꼭질 4 (0) | 2024.02.21 |
---|---|
백준 [15651] N과 M (3) (0) | 2024.02.18 |
백준 [15650] N과 M (2) (0) | 2024.02.18 |
백준 [15649] N과 M (1) (2) | 2024.02.18 |
백준 [7576] 토마토 (JAVA) (0) | 2024.02.14 |