백준 1697번

문제

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

알고리즘

1. BFS

2. 그래프 이론

풀이 

 

1. 상태 정의: 수빈이의 현재 위치와 현재까지 걸린 시간을 상태로 정의

2. 탐색 공간 제한: 위치는 0부터 100,000까지로 이 범위 안에서만 처리.

3. 방문 체크: 이미 방문한 위치를 다시 방문하지 않도록 관리

4. 이동 규칙: 수빈이가 이동할 수 있는 경우는 걷기와 순간이동 이 규칙을 적용해 다음 상태를 계산

---

 

1. 수빈이의 시작 위치에서 탐색을 시작합니다.

2. 한 번 이동할 때마다 새로운 상태를 큐에 추가하고, 방문 여부를 체크합니다.

3. 동생의 위치에 도달하면 그 시점의 시간을 출력하고 탐색을 종료합니다.

 

 

왜 BFS인가?

• BFS는 모든 경로를 동일한 "단계"에서 탐색하므로 가장 먼저 목표에 도달한 경로가 최단 경로임을 보장한다.

왜 방문 배열이 필요한가?

• BFS에서는 같은 위치를 여러 번 방문할 수 있어, 방문 배열을 사용하지 않으면 같은 위치가 중복으로 추가되어 메모리 초과가 발생한다.

코드

public class Main {
	private static final int[] move = {1, -1, 2};

	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
			int up = Integer.parseInt(stringTokenizer.nextToken());
			int under = Integer.parseInt(stringTokenizer.nextToken());

			Set<Integer> visited = new HashSet<>();

			Deque<int[]> dq = new ArrayDeque<>();
			dq.add(new int[] {up, 0});
			visited.add(up);
			while (!dq.isEmpty()) {
				int[] poll = dq.poll();
				if (poll[0] == under) {
					System.out.println(poll[1]);
					return;
				}
				for (int i : move) {
					int next;
					if (i == 2) {
						next = poll[0] * 2;
					} else {
						next = poll[0] + i;
					}
					if (next < 0 || next > 100000 || visited.contains(next)) {
						continue;
					}
					dq.add(new int[] {next, poll[1] + 1});
					visited.add(next);
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}