[Baekjoon] 12761_돌다리

Silver I

문제(출처: https://www.acmicpc.net/problem/12761)

---

< 돌다리 >

 

문제 풀이

 

bfs로  최소한의 이동 횟수를 구하였다.

 

 

 - my solution (Java)

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

public class _12761_ { // 돌다리
	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.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()); // 도착
		
		boolean visited[]=new boolean[100001];
		int answer[]=new int[100001];
		Queue<Integer>queue=new LinkedList<>();
		queue.add(N);
		visited[N]=true;
		
		while(!queue.isEmpty()) {
			int temp=queue.poll();
			int arr[]={temp-1,temp+1, temp-A,temp+ A, temp-B, temp+B, temp*A, temp*B};
			for(int i=0; i<8; i++) {
				if(arr[i]>=0 && arr[i]<=100000 && !visited[arr[i]]) {
					visited[arr[i]]=true;
					answer[arr[i]]=answer[temp]+1;
					queue.add(arr[i]);
				}
			}
			if(answer[M]>0)break;
		}
		System.out.println(answer[M]);
	}
}

 

Main

- 스카이 콩콩의 힘 (A, B), 동규의 현재 위치 (N), 주미의 현재 위치(M) 입력

- visited : 방문 여부

- answer : 이동 횟수 저장

- 동규의 현재 위치를 queue에 넣어 시작 -> queue가 빌 때까지 반복하여 현재 좌표에서 -1, +1, -A, +A, -B, +B, *A, *B 만큼 이동하여 그 위치가 범위 안이고 아직 방문하지 않았다면 방문 및 이동 횟수 저장, queue에 추가

- answer[M]이 0보다 크다면 도착했다는 뜻이므로 종료

- answer[M] 출력

---

생각🤔

 

---