백준 13913 - 숨바꼭질 4

Java

13913 번 - 숨바꼭질 4

문제

접근 방법

BFS의 성질 중, 처음 도달한 시점이 최단 거리임을 사용하여 해결하였다.

이동 내역을 구하기 위해 int[]인 int형 배열을 사용하였는데, 각 인덱스의 값에 도달하기 전 이전 경로를 저장한다.
따라서, 최종 목적지에 도착하면 위 배열을 역순으로 탐색하여 구하면 이동 경로가 된다.

한번 방문한 인덱스는, boolean[] boolean 배열을 통해 방문 처리를 하였으므로, 재방문을 하지 않는다.

코드

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

public class Main {
	static int n, result;
	static int start, end;
	static boolean[] vis;
	static int[] track;
	static final int MAX = 100000;
	static List<Integer> rList;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	start = stoi(stk.nextToken());
    	end = stoi(stk.nextToken());

    	vis = new boolean[MAX + 1];
    	track = new int[MAX + 1];
    	track[start] = -1;

    	rList = new ArrayList<>();
    	BFS(start, end);

    	br.close();
	}

	static void BFS(int start, int end) {
		Queue<Pair> queue = new LinkedList<Pair>();

		Pair pair = new Pair(start, 0);
		queue.add(pair);

		vis[start] = true;

		int curN, nextN;
		int cnt;
		while(!queue.isEmpty()) {
			pair = queue.poll();
			curN = pair.curN;
			cnt = pair.cnt;

			// 목표 지점에 도달 하였을 때
			if(curN == end) {
				System.out.println(cnt);		// 도달하는데 까지 걸린 시간 출력

				// 도달하는데 까지 이동한 내역 출력
				int idx = curN;
				while(track[idx] != -1) {
					rList.add(idx);
					idx = track[idx];
				}
				rList.add(start);
				Collections.reverse(rList);		// 순서를 역순으로 뒤집음
				for(int l : rList) {
					System.out.print(l + " ");
				}

				return;
			}

			//  X-1 , X+1로 이동
			nextN = curN - 1;
			if(nextN >= 0 && !vis[nextN]) {
				cal(nextN, cnt, queue, curN);
			}

			nextN = curN + 1;
			if(nextN <= MAX && !vis[nextN]) {
				cal(nextN, cnt, queue, curN);
			}

			// 2*X의 위치로 이동
			nextN = curN * 2;
			if(nextN <= MAX && !vis[nextN]) {
				cal(nextN, cnt, queue, curN);
			}
		}

	}

	static void cal(int nextN, int cnt, Queue<Pair> queue, int curN) {
		Pair pair = new Pair(nextN, cnt + 1);
		track[nextN] = curN;
		vis[nextN] = true;

		queue.add(pair);
	}

	static class Pair {
		int curN;
		int cnt;

		public Pair(int n, int ct) {
			curN = n;
			cnt = ct;
		}

		public int getCurN() {
			return curN;
		}

		public void setCurN(int curN) {
			this.curN = curN;
		}

		public int getCnt() {
			return cnt;
		}

		public void setCnt(int cnt) {
			this.cnt = cnt;
		}

	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점