728x90
❓ 숨바꼭질
🏷️ 관련 주제 : DFS BFS 시간복잡도
💦 나의 시도
Try01. DFS
재귀함수를 이용하여 DFS로 수빈이 이동한 점이 동생이 위치한 점과 일치하는지 탐색
⏱️ 시간 초과
작성했던 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int limit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
limit = Math.abs(N - K);
findSister(N, K, 0);
System.out.println(limit);
}
public static void findSister(int N, int K, int move) {
if (move >= limit) {
return;
}
if (N == K) {
limit = move;
return;
}
findSister(N * 2, K, move + 1);
findSister(N - 1, K, move + 1);
findSister(N + 1, K, move + 1);
}
}문제를 해결하려고 고민하였으나 권장 시간 초과😭
자정이 넘어서 다음날 아침 다른 분들이 작성한 블로그를 참고하려고 검색함.
그런데 풀이를 보기 전에 풀이 방법에 BFS도 있다는 것을 발견!
다른 분의 풀이를 보지 않고 다시 BFS로 문제를 풀어보기로 하였다.
Try02. BFS
- 수빈이의 위치
N과 동생의 위치K를BufferedReader와StringTokenizer로 입력받아 각각 int형 변수에 할당 - 수빈이의 이동 횟수를 담을 변수 int
move를 0으로 초기화 N == K이면 0을 출력- 현재 수빈의 위치를 담을 변수 int
cur을N으로 초기화 - 큐에 담은 다음 탐색 위치 개수를 담을 변수 int
in을 0으로 초기화 - 수빈이 이동할 점을 담을 객체 Queue
q에N을 추가 - 수빈이 이동한 위치와 동생의 위치가 다른(
cur != K) 동안 반복문을 돌면서 수빈의 최소 이동 횟수 탐색- 반복문 처음에
move++ - while문 안에서 for문을 돌 범위를 정하기 위한 변수 int
len을3 * in + 1로 초기화 - 이번 레벨에서 탐색할 개수
len을 초기화 했으므로in에는 다시 0을 할당 - 0 ~ (len - 1) 범위로 for문을 돌기
q에서 제일 처음 원소를 뽑아cur에 할당- 이미 탐색한 점을 담은 ArrayList
visited가cur을 포함하고 있으면continue; - 그렇지 않으면
visited에cur을 추가하고in++ q에 다음 탐색할 점cur - 1,cur + 1,cur * 2을 추가- 수빈이 이동한 위치와 동생의 위치가 같으면(
cur == K)move를 출력하고 반복문 종료
- 반복문 처음에
처음 작성한 DFS코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static int limit;
public static Queue<Integer> q = new LinkedList();
public static ArrayList<Integer> visited = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int cur = N;
int move = 0;
int checked = 0;
q.offer(N);
while (cur != K) {
move++;
int len = 3 * checked + 1;
for (int i = 0; i < len; i++) {
cur = q.poll();
if (visited.contains(cur)) {
continue;
}
checked++;
visited.add(cur);
q.offer(cur - 1);
q.offer(cur + 1);
q.offer(cur * 2);
if (cur == K) {
System.out.println(move);
break;
}
}
}
}
}❌ 틀렸습니다.
큐에 다음 탐색할 위치를 이미 담아버린 채로 꺼낼 때 이미 방문한 위치인지 체크하는 것이 문제인 것 같아서 코드 수정
- 큐에서 제일 처음 원소를 꺼내
cur == K이면move를 출력하며 코드 실행을 종료하는 부분은 동일하고 큐에 다음 탐색할 점의 위치를 담는 부분만 수정
int[] check = {cur - 1, cur + 1, cur * 2};
for (int n : check) {
if (!visited.contains(n)) {
q.offer(n);
in++;
}
}❌ 틀렸습니다.
다음 탐색할 점의 위치 n의 범위를 생각하지 않은 것 같아서 코드 수정
int[] check = {cur - 1, cur + 1, cur * 2};
for (int n : check) {
if (!visited.contains(n) && n >= 0 && n <= 100000) {
q.offer(n);
in++;
}
}💽 메모리 초과
이유를 알 수 없어 처음에 검색해 보았던 블로그의 풀이를 따라 코드를 수정해 보았음.
수정한 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static Queue<Integer> q = new LinkedList();
public static ArrayList<Integer> visited = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int move = 0;
if (N == K) {
System.out.println(move);
return;
}
int cur = N;
q.offer(N);
visited.add(N);
while (true) {
int len = q.size();
for (int i = 0; i < len; i++) {
cur = q.poll();
if (cur - 1 == K || cur + 1 == K || cur * 2 == K) {
System.out.println(move + 1);
return;
}
int n = cur - 1;
if (!visited.contains(n) && n >= 0 && n <= 100000) {
q.offer(n);
visited.add(n);
}
n = cur + 1;
if (!visited.contains(n) && n >= 0 && n <= 100000) {
q.offer(n);
visited.add(n);
}
n = cur * 2;
if (!visited.contains(n) && n >= 0 && n <= 100000) {
q.offer(n);
visited.add(n);
}
}
move++;
}
}
}⏱️ 시간 초과
이유를 알 수 없음...💀
코드를 살펴보다 DFS로 코드를 작성할 때, q와 visited를 public static으로 main 메서드 밖에서 선언해서 그런가? 하고 main 메서드 안으로 옮겨 와 보았으나...
⏱️ 시간 초과
다시 다른 사람의 풀이와 내 풀이가 뭐가 다르지? 생각하다
visited가 boolean[]로 선언되어있는 것을 발견!
다음 탐색할 점의 위치 n이 이미 탐색한 위치인지 확인하는 조건으로 !visited.contains(n)을 사용하였는데 생각해 보니 알고리즘 복잡도가 좋지 않은 것으로 판단
visited를 길이 100001의 1차원 boolean 배열로 변경
맞았습니다!!
- 메모리 : 22728 KB
- 시간 : 148 ms
- 코드 길이 : 1422 B
📑제출 기록 및 오답 원인
중간에 '맞았습니다!!'는 하도 정답이 안나와서 내가 잘못된 풀이를 찾은 건가? 싶어서 인터텟에서 찾은 풀이 제출해 봄
(내가 잘못된 풀이를 찾은 건 아니었다;;)
제일 위에가 최신 제출이므로 내가 제출한 풀이이고
3칸 아래에 제출이 인터넷에서 찾은 풀이
성능 상으로는 인터넷에서 찾은 풀이가 조금 더 좋은 것 같다.
어쨌든 고민 끝에 문제를 해결할 수 있어서 좋았다.
💯 해결 방법
내가 작성한 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int move = 0;
if (N == K) {
System.out.println(move);
return;
}
Queue<Integer> q = new LinkedList();
boolean[] visited = new boolean[100001];
int cur = N;
q.offer(cur);
visited[cur] = true;
while (true) {
int len = q.size();
for (int i = 0; i < len; i++) {
cur = q.poll();
int[] check = {cur - 1, cur + 1, cur * 2};
for (int n : check) {
if (n >= 0 && n <= 100000 && !visited[n]) {
q.offer(n);
visited[n] = true;
}
}
if (cur == K) {
System.out.println(move);
return;
}
}
move++;
}
}
}인터넷에서 찾은 풀이
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
if (n == k) {
System.out.println(0);
return;
}
boolean[] visited = new boolean[100001];
visited[n] = true;
Queue<Integer> q = new LinkedList<>();
q.add(n);
int size = q.size();
int count = 0;
while (true) {
count++;
size = q.size();
for (int i = 0; i < size; i++) {
int x = q.remove();
visited[x] = true;
if (x-1 == k || x+1 == k || x*2 == k) {
System.out.println(count);
return;
}
if (x-1 >= 0 && !visited[x-1]) {
visited[x-1] = true;
q.add(x-1);
}
if (x+1 <= 100000 && !visited[x+1]) {
visited[x+1] = true;
q.add(x+1);
}
if (x*2 <= 100000 && !visited[x*2]) {
visited[x*2] = true;
q.add(x*2);
}
}
}
}
}
🏷️ 문제 풀면서 참고한 블로그
728x90
