글 읽기 - 범위에 관한 질문.

kimby469 3년 전 0

안녕하세요. 범위에 관련해서 질문드립니다!

bfs 탐색을 통하여 인접하게 -1 +1 *2 칸 식으로 큐에 담아서 해당 위치를 몇번만에 도달하는지 구현하였습니다.

이 부분(posit[nx] == posit[cur]+1 )에서 질문이 있습니다.

해당 큐에 들어갈 조건에서 posit[nx] > posit[cur]+1 현재 큐에서 뽑은 점에서 +1 한 것이 새로운 점 nx에 도달할 때 더 짧은 거리로 접근 가능하다면 이라고 맨 처음에는 작성하였습니다. 이부분에서 반례가 있을지 궁금합니다.

(posit[nx] == posit[cur]+1 ) 이 경우는 이미 bfs 인접한 점을 계속 찾아서 해당 위치에서 가장 빠른 점으로 도달하는 방법인것을 이해는 됫는데 위 질문에 대한 반례 생각이 나질 않아 이렇게 도움을 요청하게 됬습니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int dx[] = {-1, 1, 2};
    static int n, k;
    static int posit[];
    static int minT = (int) 1e9;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str[] = sc.nextLine().split(" ");
        posit = new int[100001];
        n = Integer.parseInt(str[0]);
        k = Integer.parseInt(str[1]);
        if(n>=k)
        {
            System.out.println(n-k);
            System.out.println(1);
        }
        else {
            bfs(n);
            System.out.println(minT);
            System.out.println(cnt);
        }
    }

    static int cnt = 0;

    static void bfs(int subin) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(subin);// 수빈이의 위치를 넣고
        posit[subin] = 1; //수빈이의 위치를 처음 1로 초기화
        while (!q.isEmpty()) {
            int cur = q.poll(); // 현재 큐에서 뽑은 위치를 기반으로
            if (minT < posit[cur])
                return;
            for (int i = 0; i < 3; i++) {
                int nx = 0;
                if (i != 2) {
                    nx = cur + dx[i];
                } else {
                    nx = cur * dx[i];
                }
                if (nx < 0 || nx > 100000) continue;


                if (nx == k) {
                    minT = posit[cur];
                    cnt++;
                }
                // posit[nx] == posit[cur] + 1
                if (posit[nx] == 0 || (posit[nx] == posit[cur] + 1)) {
                    // 한번 방문하지 않았다면. -> 방문해도 상관 없지만 이전보다 거리가 크면 안됨..
                    q.add(nx);
                    posit[nx] = posit[cur] + 1; // 현재 큐에서 꺼내온 위치를 기준으로  +1;
                }
            }
        }
    }

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

범위에 관한 질문.

kimby469 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말