백준 Q1697 - 숨바꼭질

문제 및 입출력

---

풀이

수빈이이와 동생의 위치가 주어지고 동생의 위치는 바뀌지 않고, 수빈이가 동생의 위치로 최단 거리를 사용하여 몇번에 가는지 구하는 문제이다.
수빈이는 -1, +1, *2 로 이동할 수 있으므로 바로 방향 벡터를 떠올렸다.
이 중 최소의 횟수로 동생의 위치에 도달하면 되므로 모든 경우를 탐색하기 위해 BFS를 사용하자.

static int N, K;
static int[] dx = {-1, 1, 2};
static int[] result;
static boolean[] visited;

변수 설명

• N,K: 수빈이와 동생의 현재 좌표
• dx: 방향 벡터
• result: 수빈이가 몇 번째의 step으로 각 좌표에 도달하였는지 count를 하는 배열
• visited: 방문 여부를 확인하기 위한 배열

result = new int[100001];
visited = new boolean[100001];

bfs(N);
System.out.println(result[K]);

현재 위치를 바로 배열에 적용시키기 위해 100,000+1 을 하여 초기화 하였다.
X축 (1차원 배열) 에서만 움직이므로 bfs(수빈이의 초기 위치) 를 하고, 마지막에 동생의 위치의 count값을 출력하면 된다.

int step = 0;
        
while (!queue.isEmpty()) {
	step += 1;
	for (int i = queue.size(); i > 0; i--) {
		 int current = queue.poll();
         if (current == K) {
			return;
		}
		for (int j = 0; j < 3; j++) {
			int nextX = j == 2 ? current * dx[j] : current + dx[j];
			if (nextX >= 0 && nextX <= 100000 && !visited[nextX]) {
                        queue.add(nextX);
                        visited[nextX] = true;
                        result[nextX] = step;
			}
		}
	}
}

처음에는 큐에서 poll할 때 마다 step을 증가시켜줬는데 이렇게 하면 같은 단계여야하는 result의 값이 서로 달라지기 때문에 큐 사이즈 만큼 반복문을 돌리지만, while문으로 감쌀때 step을 1씩 증가시켜 주었다.
이후 큐에서 뺏을때 현재 값이 K 이면 바로 return 으로 반환하고, 아닌경우 -1,+1,*2 에 대한 탐색을 계속 진행한다.

if (nextX >= 0 && nextX <= 100000 && !visited[nextX])
여기서 nextX의 최대값 조건을 빠뜨려서 계속 너무 큰 수가 나오는 오류가 있었다.

---

최종 코드

public class Main {
    static int N, K;
    static int[] dx = {-1, 1, 2};
    static int[] result;
    static boolean[] visited;

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        result = new int[100001];
        visited = new boolean[100001];

        bfs(N);
        System.out.println(result[K]);
    }

    private static void bfs(int n) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        visited[n] = true;

        int step = 0;

        while (!queue.isEmpty()) {
            step += 1;

            for (int i = queue.size(); i > 0; i--) {
                int current = queue.poll();
                if (current == K) {
                    return;
                }
                for (int j = 0; j < 3; j++) {
                    int nextX = j == 2 ? current * dx[j] : current + dx[j];

                    if (nextX >= 0 && nextX <= 100000 && !visited[nextX]) {
                        queue.add(nextX);
                        visited[nextX] = true;
                        result[nextX] = step;
                    }
                }
            }
        }
    }
}

---

풀이 후기

result = new int[100001];
visited = new boolean[100001];

굳이 이 코드 두개를 분리할 필요가 있나 생각을 해봤다.
int형인 배열 하나로 합치고, 방문조건 또한 판단할 수 있을거라 생각하여 리팩토링 해보았다.

private static void bfs(int n) {
	Queue<Integer> queue = new LinkedList<>();
	queue.add(n);

	while (!queue.isEmpty()) {
		for (int i = queue.size(); i > 0; i--) {
			int current = queue.poll();
			if (current == K) {
				return;
		}
		for (int j = 0; j < 3; j++) {
			int nextX = j == 2 ? current * dx[j] : current + dx[j];
			
            if (0 <= nextX && nextX <= 100000 && visited[nextX] == 0) {
                        queue.add(nextX);
                        visited[nextX] = visited[current] + 1;
			}
		}
	}
}

초기 배열은 0으로 초기화 되어있으므로, visited[next] == 0 으로 방문여부를 체크하자

리팩토링 과정에서 step 변수 또한 굳이 사용할 필요가 없다고 생각이 들었다.
visited[nextX] = visited[current] + 1 로 코드를 수정하여, 현재 인덱스의 값에서 +1을 해주면 된다.