AOJ -95 Brr Brr Patapim - BFS

 

핵심 아이디어

다이얼 한 번 = 4가지 중 하나

분 +1  → 59 넘으면 시 +1 (연동!)
분 -1  → 00 밑으로 가면 시 -1 (연동!)
시 +1
시 -1

분을 돌릴 때 시가 바뀔 수 있어서 시/분이 독립적이지 않음 → BFS로 모든 경우 탐색.

---

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] cur = br.readLine().split(":");
        String[] tar = br.readLine().split(":");

        int startH = Integer.parseInt(cur[0]);
        int startM = Integer.parseInt(cur[1]);
        int endH   = Integer.parseInt(tar[0]);
        int endM   = Integer.parseInt(tar[1]);

        System.out.println(bfs(startH, startM, endH, endM));
    }

    static int bfs(int startH, int startM, int endH, int endM) {
        int[][] dist = new int[24][60];
        for (int[] row : dist) Arrays.fill(row, -1);

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startH, startM});
        dist[startH][startM] = 0;

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            int h = now[0], m = now[1];

            int[][] nexts = {
                {h, (m + 1) % 60},       // 분 +1
                {h, (m - 1 + 60) % 60},  // 분 -1
                {(h + 1) % 24, m},        // 시 +1
                {(h - 1 + 24) % 24, m}   // 시 -1
            };

            for (int[] next : nexts) {
                int nh = next[0], nm = next[1];
                if (dist[nh][nm] == -1) {
                    dist[nh][nm] = dist[h][m] + 1;
                    if (nh == endH && nm == endM) return dist[nh][nm];
                    queue.add(new int[]{nh, nm});
                }
            }
        }

        return dist[endH][endM];
    }
}

---

BFS 흐름

시작: [startH, startM] 큐에 넣기

반복:
 ├─ 큐에서 현재 상태 꺼내기
 ├─ 4방향으로 다이얼 돌리기
 │    ├─ 처음 방문한 상태면 dist + 1 기록
 │    └─ 목표 도달하면 즉시 반환
 └─ 큐가 빌 때까지 반복

전체 상태가 24 × 60 = 1440개뿐이라 BFS가 매우 빠릅니다.