문제 구성 📖
코딩테스트 사이트 : 백준
난이도 : 실버1
풀이 날짜 : 2022.06.18
사용한 풀이 방법 : DFS, BFS
문제링크
https://www.acmicpc.net/problem/1697
풀이법
수빈이가 동생위치까지 이동하는
최단 이동횟수를 구하는 문제이다.
- 일단 수빈이가 이동할 수 있는 방법은 3가지이다.
- 그리고 또 이동할 수 있는 방법은 또 다시 3가지이다.
- DFS로 예상 시간 복잡도 3^n 이 나올것 같지만,
- 우선순위를 잘 두면서 하면 가능할거 같아 보인다.
수빈이랑 동생의 위치 상황은 3가지이다.
- 수빈이 위치 > 동생의 위치
- 수빈이 위치 < 동생의 위치
- 수빈이 위치 == 동생의 위치
그럼 각 상황에서 취할 수 있는 행동은 다음과 같다.
- 수빈이 위치 > 동생의 위치 :
x-1=> 시간 복잡도 N 이다. - 수빈이 위치 < 동생의 위치 :
2x,x+1=> 시간 복잡도 2^N이다. - 수빈이 위치 == 동생의 위치 : 리턴
주의사항
- 여기서 함정이 있는데,
- 예를 들어
- 수빈이 위치 > 동생의 위치
x-1을4번해야되는데, - 앞에서
2x가 있었을 경우 앞에서x-1을2번만 해줘도 된다.
- 수빈이 위치 > 동생의 위치
해결방안
2x를 한 횟수를 별도로 세고, 횟수에 맞춰..수빈이 위치 - 동생의 위치= 나온 값(diff)을2^n으로 나눈 몫 만큼 더한다.
알고리즘 설계
- DFS를 설계한다.
- 수빈이의 위치가 동생의 위치보다 클 경우(
수빈 > 동생) 함수로 구현해준다. - 이동횟수가 가장 작은 숫자를 출력한다.
주어지는 조건
- N(수빈의 위치) (최대 10만)
- K(동생의 위치) (최대 10만)
public class HideAndSeek {
static int minValue = Integer.MAX_VALUE;
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 count = 0;
int multiTwoCount = 0;
DFS(K,N,0,0);
System.out.println(minValue);
br.close();
}
public static void DFS(int K, int curLocation, int count, int multiTwoCount) {
if(count > minValue){ // 시간초과가 떠서 추가한 코드, 쓸데없는 계산 버림
return;
}
if (curLocation >= K) {
int addCount = moveCalculate(multiTwoCount, curLocation - K);
count += addCount;
if (minValue > count) {
minValue = count;
}
return;
}
//if (curLocation < K)
DFS(K, curLocation * 2, count + 1, multiTwoCount + 1);
DFS(K, curLocation + 1, count + 1, multiTwoCount);
}
public static int moveCalculate(int multiTwoCount, int diff) {
int div = (int) Math.pow(2, multiTwoCount);
int move = 0;
while (diff > 1) {
if ((diff / div) > 0) move += (diff / div);
diff = diff % div;
div /= 2;
}
if (diff == 1) move++;
return move;
}
}-
하지만 그 결과는 아래와 같다.
-
DFS로는 메모리 초과가 나온다.
BFS
- 최단 이용횟수를 구하기위해서 보다 효율적인 BFS를 사용하고자 한다.
- 위 그림에서, 1,2,3중 하나라도, 동생위치에 도달하는 순간
Depth를 반환하면,- 나머지 불필요한 곳을 확인안해도 된다.
- 또한, 이미 방문했던 숫자는 제외 시켜준다.
- 여기서 중요한 것은
Depth의 값을 유지하는 것과 방문했는지 유무를 파악하는 것! - 방법은 여러 방법이 있겠지만, 가장 먼저 생각난 방법은 2가지이다.
- Queue에 값을 저장할 때, 같이 저장(Map,Class)하거나,
- Queue를 두개 만들어서 Depth도 관리해 줄 수 있다.
- 난 전자를 택했다.
public class HideAndSeek {
static int K ;
static int N ;
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()); //동생 위치
Queue<Depth> locationQue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
Depth depth= new Depth(N, 0);
locationQue.add(depth);
int curLocation ;
int curDepth = 0;
while (!locationQue.isEmpty()){
curLocation = locationQue.peek().getLocation();
curDepth = locationQue.peek().getDepth();
locationQue.poll();
//방문했던 곳 다시 가기 방지
if(visited.contains(curLocation)){continue;}
visited.add(curLocation);
// 탈출 조건
if(curLocation == K){
break;
}
// 3가지 경우 적용하기
locationQue.add(new Depth(curLocation - 1,curDepth + 1));
locationQue.add(new Depth(curLocation + 1,curDepth+1));
locationQue.add(new Depth(curLocation * 2,curDepth+1));
}
System.out.println(curDepth);
br.close();
}
}
class Depth{
private int location;
private int depth;
public Depth(int location, int depth) {
this.location = location;
this.depth = depth;
}
public int getLocation() {
return location;
}
public int getDepth() {
return depth;
}
}- 그래도 메모리가 초과된다.
- 그래서 결국 다른 래퍼런스를 참고하였다.
- 얻은 힌트 :
visited[]를int[]로 만들어, 요소의 값을depth을 넣어준다.- 여기서 중요한 점은, 방문하기전에 방문할 값을 넣어줘야한다는 것!
package Beakjoon;
import java.io.*;
import java.util.*;
// BFS
public class HideAndSeek {
static int K ;
static int N ;
static int[] visited = new int[100001];
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()); //동생 위치
Queue<Integer> locationQue = new LinkedList<>();
locationQue.add(N);
visited[N] = 1;
int curLocation ;
while (!locationQue.isEmpty()){
curLocation = locationQue.poll();
// 목표 도달
if(curLocation == K){
System.out.println(visited[K] -1 );
break;
}
//방문했던 곳인지 파악하면서 3가지 경우 적용하기
if((curLocation-1) >= 0 && visited[curLocation- 1] == 0 ) {
locationQue.add(curLocation - 1);
visited[curLocation - 1] = visited[curLocation] + 1;
}
if((curLocation +1) < 100001 && visited[curLocation + 1] == 0 ) {
locationQue.add(curLocation + 1);
visited[curLocation + 1] = visited[curLocation] + 1;
}
if((curLocation * 2) < 100001 && visited[curLocation * 2 ] == 0) {
locationQue.add(curLocation * 2);
visited[curLocation * 2] = visited[curLocation] + 1;
}
}
br.close();
}
}주어진 값이 다음과 같을 때 테스트를 해보자
0 0
0 100000
100000 0
- 이 중 하나라도 실패하면, 통과하질 못한다.
느낀점😌
- 그래프 문제에서 완전탐색은 필수로 할줄 알아야하며, 그중 가장 기본이 되는 것이 BFS, DFS인 것같다.
- BFS,DFS의 원리를 알고 흐름을 깨우쳐야 상황에 따라 응용하면서 사용할 수 있는 것 같다.
- 또한, BFS, DFS의 필수요소인 visited에 대해 확실하게 잡고 갈 수 있는 문제이어서, 만약 그래프 관련 공부를 하고 있다면 추천해주고 싶은 문제이다.
한단계씩 올라가는 개발자