백준 - 1697(숨바꼭질, 자바)

문제

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

문제 접근

• 출력할 값 : 두 위치 N과 K에서 N이 +1, -1, *2의 연산을 활용해 K에 도달하는 방법의 최소 횟수
• BFS로 만들 수 있는 모든 경우를 구해가며 K와 같아지면 리턴

DFS vs BFS

• 만약 dfs로 모든 수를 다 만드려면 +1로 만들 수 있는 수를 모두 만들고 거기서 리턴해서 -1을 추가해 만들 수 있는 수를 모두 만들고 거기서 리턴해서 *2를 추가해 만들 수 있는 수를 모두 만들고 그 중에서 정답 값을 찾는다.

→ 직접 구현해보니 stackoverflow가 발생한다.(만약 입력 값이 작다고쳐도 연산이 너무 많다.)

• bfs로 구현하면 위에 그림과 같은 로직으로 연산 4번만에 k 값을 찾고 종료한다.
• 따라서 해당 문제는 bfs로 구현하도록 설계된 문제이다.

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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());

		System.out.println(bfs(n, k));

	}

	static int[] visited = new int[200001];

	static int bfs(int start, int end) {
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		visited[start] = 1; // 1빼고 출력해도 되나 확인하기
		while (q.size() != 0) {
			int current = q.poll();
			if (current == end) {
				return visited[end] - 1;
			}
			// 3가지 조건 모두 적용해보기
			// 1칸 전진한 값이 범위 안이고 아직 안 만들어본 값일 때
			if (current + 1 >= 0 && current + 1 <= 200000 && visited[current + 1] == 0) {
				q.add(current + 1);
				visited[current + 1] = visited[current] + 1;
			}
			// 1칸 후진한 값이 범위 안이고 아직 안 만들어본 값일 때
			if (current - 1 >= 0 && current - 1 <= 200000 && visited[current - 1] == 0) {
				q.add(current - 1);
				visited[current - 1] = visited[current] + 1;
			}
			// *2한 값이 범위 안이고 아직 안 만들어본 값일 때
			if (current * 2 >= 0 && current * 2 <= 200000 && visited[current * 2] == 0) {
				q.add(current * 2);
				visited[current * 2] = visited[current] + 1;
			}
		}
		return -1;
	}

}

회고

• dfs와 bfs에 대한 이해도가 높으면 풀 수 있는 문제
• bfs를 이차원 탐색에서만 써봐서 많이 헷갈렸고 인터넷 자료보고 알았다…
• dfs와 bfs에 대해 다시 생각해볼 수 있는 문제라 다들 풀어보길 바람.

뻘짓했던 코드(dfs로 구현 시도)

static int ans;
	static void dfs(int start, int end, int tmp) {
		//값을 찾았을 때
		if(start == end) {
			ans = tmp;
			return;
		}
		// 값이 조건에서 벗어나 더 연산해도 못 찾을 때
		if(start <=0 || start > end) {
			return;
		}
		//3가지 경우를 모두 탐색
		dfs(start+1, end, tmp+1);
		//이전 값으로 리턴했으니 연산횟수 -1 
		tmp -= 1;
		dfs(start-1, end, tmp+1);
		tmp -= 1;
		dfs(start*2, end, tmp+1);
		
	}
//stackoverflow

위 경우 값을 찾아 return해도 stack 메모리에 있는 dfs를 모두 시행해야한다.

따라서 답을 찾으면 종료되었던 bfs와 달리 강제로 모든 경우를 다 해봐야한다.

심지어 메모리에 있는 dfs 메서드가 다시 dfs 메서드를 호출하기 때문에 너무 많다.

따라서 stack의 메모리가 넘쳐 stackoverflow가 발생한다.

 

이걸 재귀로 만들 생각을 한 내가 신기하다…그래도 덕분에 공부많이 됐다..