[백준]1697 숨바꼭질 | 그래프, BFS | 실버 Ⅰ | JAVA

📌 문제

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

 

✅ 정답 코드

import java.io.*;
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 a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        
        System.out.println(bfs(a, b));
    }
    public static int bfs(int start, int end) {
        boolean[] visited = new boolean[100001];
        Queue<int[]> q = new LinkedList<>();
        
        q.add(new int[]{start,0});
        visited[start] = true;
        
        while (!q.isEmpty()){
            int [] current = q.poll();
            int position = current[0];
            int time = current[1];
            
            if (position == end) return time;
            
            for (int nextPos : new int[]{position-1, position+1, position*2}) {
                if (nextPos>=0 && nextPos<=100000&&!visited[nextPos]){
                    visited[nextPos] = true;
                    q.add(new int[]{nextPos, time+1});
                }
            }
        }
        return -1;
    }
}

 

1️⃣ visited 배열

boolean[] visited 배열을 사용하여 각 위치에 방문했는지를 기록합니다. visited 배열의 크기는 100001로 설정하여 0부터 100000까지의 위치를 모두 포함합니다.

2️⃣ 큐

Queue<int[]> q를 사용하여 BFS를 위한 큐를 초기화합니다. 큐에는 위치와 현재 시간을 담은 배열이 추가됩니다.

q.add(new int[]{start, 0})를 통해 수빈이의 시작 위치와 시간을 큐에 추가합니다.

visited[start] = true로 수빈이의 시작 위치를 방문했다고 표시합니다.

3️⃣ BFS 탐색

while (!q.isEmpty()) 루프를 통해 큐가 빌 때까지 반복합니다.

q.poll()을 사용하여 큐에서 현재 위치와 시간을 꺼냅니다.

if (position == end) 조건문으로 현재 위치가 동생의 위치와 같다면, 현재 시간을 반환합니다.

4️⃣ 다음 위치 계산

for 루프를 사용하여 걷기와 순간이동으로 갈 수 있는 세 가지 위치를 계산합니다.

그리고 각 다음 위치에 대해 범위 체크( nextPos >= 0 && nextPos <= 100000 )와 방문 체크( !visited[nextPos] )를 합니다.

조건을 만족하는 경우, 해당 위치를 방문 처리하고 큐에 추가합니다. 시간을 1 증가시킵니다

 

---

 

공부의 흔적