mingssssss

1. 문제

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

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    
    // 전역 변수 설정
	static int[] list;
	static int[] answer;
	static int cnt;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		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());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		list = new int[M + 1];
		answer = new int[100001];

		bfs(A, B, N, M, list, answer);

	}

	private static void bfs(int A, int B, int N, int M, int[] list, int[] answer) {

		Queue<Integer> q = new LinkedList<>();

		q.add(N);

		int[] move = { 1, -1, -A, A, -B, B};
		int[] jump = {A, B};
		cnt = 0;
		
		while (!q.isEmpty()) {

			int size = q.size();

			for (int k = 0; k < size; k++) {

				int now = q.poll();
                
                // 6방향 탐색
				for (int i = 0; i < 6; i++) {

					int next = now + move[i];

					if (next < 0 || next >= 100001) {
						continue;
					}

					if (answer[next] != 0) {
						continue;
					}
					
					if (next == M) {
						System.out.println(cnt + 1);
						return;
					}
					answer[next] = answer[now] + 1;
					q.add(next);

				}
				
                // 나머지 2방향 탐색
				for (int i = 0; i < 2; i++) {

					int next = now * jump[i];

					if (next < 0 || next >= 100001) {
						continue;
					}

					if (answer[next] != 0) {
						continue;
					}
					
					if (next == M) {
						System.out.println(cnt + 1);
						return;
					}
					answer[next] = answer[now] + 1;
					q.add(next);

				}


			}
			cnt++;

		}

	}

}

3. 리뷰

현재 위치에서 +1, -1, +A, -A, +B, -B, 현재위치 * A, 현재위치 * B

로 이동하여 최솟값으로 M 지점에 도착하는 문제이다.

처음에 문제를 잘못 이해해서 현재 위치에서 A * A, B * B 만큼 이동하는 줄 알고

코드를 짰다.. 문제를 잘 읽어보는 습관을... 언제쯤 들일까...

그 이외에는 전형적인 bfs 문제이다. 메모리, 시간 둘 다 잡은 문제였다.