(BOJ) 숨바꼭질_1679번
문제
https://www.acmicpc.net/problem/1697
접근
처음에는 DFS를 먼저 떠올렸지만 풀다보니 어디서 멈춰야 할지? 과연 이 길을 통해 최적의 경로를 찾을 수 있을지 애매하다고 느껴 결국 BFS로 접근하여 풀게 되었다.
문제 자체는 어렵지는 않지만 쓸데없는(틀린) 생각을 코드에 반영하느라 시간을 날렸던 것 같다.
틀린 생각 1
수빈이와 동생의 위치를 입력받고 무조건 수빈이의 위치 <= 동생의 위치 (N <= K)로 두면 문제가 간단해질 것
if (n > k) {
int tmp = n;
n = k;
k = tmp;
}
이렇게 둘의 위치를 바꾸는 구문을 넣었는데...
반례
순간이동 시 X(수빈이의 현재 위치) * 2 로 이동 가능하다.
하지만 둘의 위치를 바꿔버리면 X / 2도 가능하다는 말이 되기 때문에 문제의 조건에 맞지 않다.
틀린 생각 2
방문 여부에 대한 배열의 크기를 수빈이의 위치와 동생의 위치 중 더 큰 값 + 1로 두면 된다.
int size = Math.max(n, k) + 1;
visited = new boolean[size];
생각이 좀 짧았다. +1 대신 +2를 하면 가능한 이야기다.
반례
N = 15, K = 29
15 -> 30 -> 29 로 답은 2가 된다.
하지만, 위처럼 코드를 작성해버리면 visited의 max index는 29가 되어버리고 (size = 29 + 1 = 30 이므로) 30 지점에 방문하지 못하게 된다.
코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static boolean[] visited = new boolean[100001];
static int n;
static int k;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] inputs = br.readLine().split(" ");
n = Integer.parseInt(inputs[0]);
k = Integer.parseInt(inputs[1]);
Queue<Integer> q = new LinkedList<>();
q.add(n); // 위치
q.add(0);
while (!q.isEmpty()) {
int num = q.remove();
int count = q.remove();
visited[num] = true;
if (num == k) {
bw.write(Integer.toString(count));
break;
}
if (0 <= num * 2 && num * 2 < visited.length && !visited[num * 2]) {
q.add(num * 2);
q.add(count + 1);
}
if (0 <= num + 1 && num + 1 < visited.length && !visited[num + 1]) {
q.add(num + 1);
q.add(count + 1);
}
if (0 <= num - 1 && num - 1 < visited.length && !visited[num - 1]) {
q.add(num - 1);
q.add(count + 1);
}
}
bw.flush();
bw.close();
br.close();
}
}
참고
넉넉히 문제의 입력값 범위를 고려하여 visited 배열의 크기를 100001로 두긴 했는데 위에서 말했던 것 처럼 수빈이와 동생의 위치의 최댓값 + 2로 해도 정답이다. 오히려 탐색 범위가 줄어들어서 좋을지도 모르겠다.
위가 최댓값 + 2, 아래가 100001로 적용했을 때인데 별 차이는 없더라... 메모리 크기에 집착하다 실수하느니 넉넉히 주고 풀어도 무방할 것 같다.
Author And Source
이 문제에 관하여((BOJ) 숨바꼭질_1679번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jduckling_1024/BOJ-숨바꼭질1679번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)