[백준 / JAVA] 13549. 숨바꼭질3

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

13549번: 숨바꼭질 3

 

---

💻 풀이 결과

💯 최종 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Node {
	int num, cnt;

	Node(int num, int cnt) {
		this.num = num;
		this.cnt = cnt;
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();

		Queue<Node> queue = new LinkedList<>();
		boolean[] visited = new boolean[100001];

		queue.add(new Node(N, 0));
		visited[N] = true;
		int next;

		while (!queue.isEmpty()) {
			Node curr = queue.poll();

			// 동생을 찾았다.
			if (curr.num == K) {
				System.out.println(curr.cnt);
				break;
			}

			// 0초 후 순간이동
			next = curr.num * 2;
			if (next >= 0 && next < 100001 && !visited[next]) { // next 범위 체크 중요!!
				queue.add(new Node(next, curr.cnt));
				visited[next] = true;
			}

			// 1초 후 걷기이동
			next = curr.num - 1;
			if (next >= 0 && next < 100001 && !visited[next]) {
				queue.add(new Node(next, curr.cnt + 1));
				visited[next] = true;
			}
			next = curr.num + 1;
			if (next >= 0 && next < 100001 && !visited[next]) {
				queue.add(new Node(next, curr.cnt + 1));
				visited[next] = true;
			}
		}
	}
}

💬 풀이 과정

• 순간이동 시에는 curr.cnt를 증가시키지 않는다.
• 걷기 이동 시에는 curr.cnt를 증가시킨다.
• visited 배열을 통해 방문 검사를 하고 BFS를 돌리면서 방문체크를 꼭 해준다.
• 1697. 숨바꼭질 문제와 동일하게 풀었다.

💡 깨달은 점

1. 방문 검사와 방문 체크 잘하기!

• 방문하지 않은 것만 BFS를 돌리고 BFS가 돌면 방문 체크를 꼭 해주어야 한다.